[R30D]路径第K小 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个 $N \times M$ 的网格，每个单元格 $(i, j)$（$1 \le i \le N, 1 \le j \le M$）上都有一个整数 $A_{i,j}$。

一条从 $(1, 1)$ 到 $(N, M)$ 的路径被定义为：从 $(1, 1)$ 开始，每次只能向右或向下移动一个单元格，最终到达 $(N, M)$ 所经过的单元格序列。

任何一条这样的路径都恰好由 $N+M-1$ 个单元格组成。这些单元格上的数字构成了一个多重集。

给定一个整数 $K$，你的任务是找到一条从 $(1, 1)$ 到 $(N, M)$ 的路径，使得该路径对应的多重集中，第 $K$ 小的元素值最大。请输出这个可能的最大值。

注意：第 $K$ 小是指将多重集中的所有数字升序排序后，位于第 $K$ 个位置的数。

格式

输入格式

第一行包含三个整数 $N, M, K$。

接下来 $N$ 行，每行包含 $M$ 个整数，表示网格上每个单元格的数字 $A_{i,j}$。

输出格式

输出一个整数，表示所有合法路径中，能得到的最大的第 $K$ 小值。

样例

样例输入 #1

3 3 3
1 8 3
9 2 5
4 7 6

样例输出 #1

6

数据规模

对于 $30\%$ 的数据，$1 \le N, M \le 10$。

对于 $100\%$ 的数据，$1 \le N, M \le 1000$，$1 \le K \le N+M-1$，$1 \le A_{i,j} \le 10^9$。