顺手牵羊

题目描述

小瑞进入了一个 $n$行 $n$列的二维数组。数组中每个位置都有一只羊，第 $i$行第 $j$列的羊的重量是 $a_{i,j}$。

小瑞一开始在 $a_{1,1}$的位置，每次可以往右一步或者往下一步。即可以从 $a_{i,j}$走到 $a_{i+1,j}$或者 $a_{i,j+1}$。但是不能走出这个数组，即不能走到下标小于 $1$或大于 $n$的位置。他走到 $a_{n,n}$就会停下。

他每次到达一个位置就会牵走那里的羊，显然最终他一共走了 $2n-1$步，牵走了 $2n-1$头羊。小珅会在这些羊中拿出最重的 $k$只羊送给 Kitten 作为她 $10$月 $9$日的生日礼物。他希望这些羊都足够重，他想知道所有牵羊方案中，哪种方案的最重的 $k$只羊中最轻的那只羊最重。

说人话就是，从 $a_{1,1}$走到 $a_{n,n}$，每次只能向右或者向下，求路径上的数中的第 $k$名最大是多少。

输入格式

两个数 $n, k$。

接下来 $n$行，每行 $n$个数，第 $i$行第 $j$列为 $a_{i,j}$。

输出格式

输出第 $k$大的数最大是多少。

输入输出样例

输入 #1

3 3
1 6 5
8 4 7
9 2 1

输出 #1

5

输入 #2

5 5
52 92 99 100 89
13 98 47 44 13
11 93 40 39 81
32 66 22 52 28
21 18 29 85 52

输出 #2

81

输入 #3

5 7
65 47 52 52 17
84 46 59 45 8
40 100 39 89 84
51 21 55 38 5
8 34 26 24 11

输出 #3

45

说明/提示

对于 $100\%$的数据，$1 \le n \le 1000$，$1 \le k \le 2n-1$，$1 \le a_{i,j} \le 10^{9}$。

子任务 $1$（$10$分）：保证所有 $a_{i,j}$都相等。

子任务 $2$（$20$分）：保证 $k = 1$。

子任务 $3$（$30$分）：保证 $n = 5$。

子任务 $4$（$40$分）：没有特殊限制。