<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 lt(const vector<vector<int>>& mat,int target,int idx,int k){
        if(target < 0){
            return 0;
        }
        if(idx >= mat.size()){
            return 1;
        }
        if(dp[idx].count(target)){
            return dp[idx][target];
        }
        unsigned long long ret = 0;
        for(auto n:mat[idx]){
            int a = lt(mat,target - n,idx+1,k); 
            ret += a;
            if(ret > k){
                break;
            }
            
        }
        dp[idx][target] = ret;
        return ret;
    }
    vector<map<int,int>> dp;
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int row = mat.size();
        dp.resize(row);  
        int lo = 0;
        int hi = 0;
        for(int i = 0;i < row;++i){
            lo += mat[i][0];
            hi += mat[i].back();
        } 
        int ans = 0;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            auto amount = lt(mat,mid,0,k); 
            if(amount >= k){
                ans = mid;
                hi = mid-1;
            }
            else{
                lo = mid+1;
            }
        }
        return ans;
    }
};
70493