<p>You are given an <code>m x n</code> matrix <code>mat</code> that has its rows sorted in non-decreasing order and an integer <code>k</code>.</p>

<p>You are allowed to choose <strong>exactly one element</strong> from each row to form an array.</p>

<p>Return <em>the </em><code>k<sup>th</sup></code><em> smallest array sum among all possible arrays</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,3,11],[2,4,6]], k = 5
<strong>Output:</strong> 7
<strong>Explanation:</strong> Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,3,11],[2,4,6]], k = 9
<strong>Output:</strong> 17
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
<strong>Output:</strong> 9
<strong>Explanation:</strong> Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.  
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat.length[i]</code></li>
	<li><code>1 &lt;= m, n &lt;= 40</code></li>
	<li><code>1 &lt;= mat[i][j] &lt;= 5000</code></li>
	<li><code>1 &lt;= k &lt;= min(200, n<sup>m</sup>)</code></li>
	<li><code>mat[i]</code> is a non-decreasing array.</li>
</ul>

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        priority_queue<int> pq;
        int n = mat.size(), m = mat[0].size();

        vector<int> prevSum;
        int total = 0;
        prevSum.push_back(0);
        for(int i=0; i<n; i++) {
            total += mat[i][0];
            for(int j=1; j<m; j++) {
                int temp = mat[i][j] - mat[i][0];
                for(int x=prevSum.size()-1; x>=0; x--)
                {
                // for(auto a : prevSum){  
                    pq.push(temp + prevSum[x]);
                    // cout<<temp+a<<' ';
                    if(pq.size() > 200)
                        pq.pop();
                }
            }
            cout<<"#"<<endl;
            prevSum.clear();
            while(!pq.empty()) {
                prevSum.push_back(pq.top());
                pq.pop();
            }
            cout<<endl;

            for(auto a : prevSum) {
                pq.push(a);
            }
            prevSum.push_back(0);
        }

        reverse(prevSum.begin(), prevSum.end());
        
        for(auto a : prevSum) {
            cout<<a<<'|';
        }
        // cout<<total + prevSum[k-2];
        return total + prevSum[k-1];
    }
};



// class Solution {
// public:
//     int kthSmallest(vector<vector<int>>& mat, int k) {
//         priority_queue<pair<int,int>> pq;
//         // val, ind_arr
//         int n=mat.size(),m=mat[0].size();
//         int sum=0;
//         vector<int> total;
//         for(int i=0;i<n;i++){
//             sum+=mat[i][0];
//             for(int j=1;j<m;j++){
//                 total.push_back(mat[i][j]-mat[i][j-1]);
//             }
//         }
//         sort(total.begin(),total.end());
//         int curr=0;
//         int ind=0;
//         while(k>0){
//             if(k-curr>=0){
//                 k-=curr;
//                 curr++;
//                 sum+=total[ind++];
//             }
//             else break;
//         }
        
//         for(auto a: total)
//             cout<<a<<' ';
        
//         cout<<endl;
//         cout<<total.size()<<' '<<k;
//         return sum + total[k-2];
//         int rem=k%n;

//         cout<<sum<<endl;
//         return sum;
//     }
// };
12878