题目背景

微隙在所必乘，微利在所必得。少阴，少阳。

题目描述

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

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

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

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

输入格式

两个数 $n,k$。

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

输出格式

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

3 3
1 6 5
8 4 7
9 2 1

5

可以走 1->6->5->7->1 这条路，这样第 $3$ 重的羊的重量是 $5$，其他方案都不如这个方案。

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

81

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

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 分）：没有特殊限制。