题目描述

小瑞进入了一个 $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$分）：没有特殊限制。

5 6
492541962 9198885 123377470 179949641 998969965
295390727 37462095 980640180 743567511 18611085
392268042 612570853 144813441 673862942 652190363
316359901 360317625 168039302 604395264 189121326
375100597 442663374 764651386 451515198 54154762

451515198

5 6
387550982 626029330 780566159 380415912 701922943
686191060 587213804 82919706 715070994 572266384
449383758 59977600 831732043 149604698 502677556
36510424 300140733 49078014 906410050 555483515
896751088 66473487 333355480 613289390 388929810

502677556

5 8
961270517 439305872 987114009 190860778 433203722
847706548 179986351 20625023 635049549 707970612
982555782 1217230 896475163 524813385 23423447
186622988 796701879 782921419 226538245 645751759
560170165 833420397 605539449 737338808 191612535

191612535