540. Find Kth Smallest Sum of a Matrix with Sorted Rows

Given a matrix where each row is sorted in ascending order, choose exactly one element from each row to form a sum. Return the k-th smallest such sum among all possible choices. The input is JSON {matrix, k}.

Input: JSON {matrix, k}.

Output: Integer — the k-th smallest row-choice sum.

Examples

Input: {"matrix":[[1,3,11],[2,4,6]],"k":5}
Output: 7
Explanation: 5th smallest combined sum.

Input: {"matrix":[[1,11],[2,4],[3,7]],"k":9}
Output: 19
Explanation: 9th smallest sum.

Input: {"matrix":[[1]],"k":1}
Output: 1
Explanation: Single choice.

Constraints

• 1<=rows<=40
• 1<=cols<=40
• 1<=k<=product of row sizes

Asked by