Find the Kth Smallest Sum of a Matrix With Sorted Rows
You are given an m x n matrix mat that has its rows sorted in non-decreasing order and an integer k.
You are allowed to choose exactly one element from each row to form an array.
Return the k^th smallest array sum among all possible arrays.
Example 1
1 3 11 2 4 6
Input
mat = [[1,3,11],[2,4,6]], k = 5Output
7Choosing one element from each row, the first k smallest sums are [1,2], [1,4], [3,2], [3,4], and [1,6], so the 5th sum is 7.
Example 2
1 3 11 2 4 6
Input
mat = [[1,3,11],[2,4,6]], k = 9Output
17The 9th smallest sum among all possible arrays formed by choosing one element from each row is 17.
Constraints
- m == mat.length
- n == mat.length[i]
- 1 <= m, n <= 40
- 1 <= mat[i][j] <= 5000
- 1 <= k <= min(200, n^m)
- mat[i] is a non-decreasing array.