说明

给你一个 $m$ * $n$ 的矩阵 mat，以及一个整数$k$，矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 $k$ 个最小数组和。

输入格式

一个 $m$ * $n$ 的矩阵 mat，以及一个整数$k$

输出格式

所有可能数组中的第 $k$ 个最小数组和

样例

2 3
1 3 11
2 4 6
5

7

样例1解释：

从每一行中选出一个元素，前 k

[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。

2 3
1 3 11
2 4 6
9

17

3 3
1 10 10
1 4 5
2 3 6
7

9

样例3解释：

从每一行中选出一个元素，前 k

[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。

2 3
1 1 10
2 2 9
7

12

数据范围

$m == mat.length$

$n == mat.length[i]$

$1 \leqslant m, n \leqslant 40$

$1 \leqslant k \leqslant min(200, n^m)$

$1 \leqslant mat[i][j] \leqslant 5000$

$mat[i]$ 是一个非递减数组

来源

LeetCode 1439