99991338 - 呆唯和递增序列 II
呆唯得到了一个 N 行 M 列的二维数组,每个元素是一个整数。
如果从第 1 行到第 N 行,依次在每一行中选取一个数,构成长度为 N 的序列,那么一共有 M^N 种选取方案。
由于她喜欢递增的序列,她把在上述的选取方案所构成的序列中,所有的严格递增的前缀都列了出来!
她把每一个前缀的数字加起来,每个前缀就对应了一个和。她把这些和升序排序,请问排序后的第 k 个数是多少?
Input
输入的第一行包含三个整数: N, M, k,代表数组的行数和列数 (1 \leq N, M \leq 1000, 1 \leq k \leq min(1000, 严格递增的前缀数量)) 。
接下来 N 行描述数组,每行输入 M 个用空格隔开的整数 x (1 \leq x \leq 10^8)。
Output
输出一个整数:把按照方案选取出的所有严格递增前缀之和排序后,第 k 个数的值。
Examples
Input
3 4 5 2 5 7 6 6 10 9 7 7 10 7 9
Output
8
Hint
样例中的 3 行 4 列数组如下:
2 5 7 6
6 10 9 7
7 10 7 9
共有 35 个严格递增前缀,这些前缀以及对应的和为:
2 :2
2 6 :8
2 6 7 :15
2 6 10 :18
2 6 7 :15
2 6 9 :17
2 10 :12
2 9 :11
2 9 10 :21
2 7 :9
2 7 10 :19
2 7 9 18
5 :5
5 6 :11
5 6 7 :18
5 6 10 :21
5 6 7 :18
5 6 9 :20
5 10 :15
5 9 :14
5 9 10 :24
5 7 :12
5 7 10 :22
5 7 9 :21
7 :7
7 10 :17
7 9 :16
7 9 10 :26
6 :6
6 10 :16
6 9 :15
6 9 10 :25
6 7 :13
6 7 10 :23
6 7 9 :22
其中第 5 小的数为 8。