3929: 顺手牵羊(挖土机 CSP-J 模拟赛 ~ 第九场)

33DAI 进入了一个 $�$ 行 $�$ 列的二维数组。数组中每个位置都有一只羊，第 $�$ 行第 $�$ 列的羊的重量是 ${�}_{�,�}$。

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

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

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

两个数 $�,�$。

接下来 $�$ 行，每行 $�$ 个数，第 $�$ 行第 $�$ 列为 ${�}_{�,�}$。

3 3
1 6 5
8 4 7
9 2 1

5