You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个 $n$ 行 $m$ 列的网格。网格里的每个格子都写着一个整数，其中第 $i$ 行第 $j$ 列的格子里写着整数 $a_{i,j}$ 。从 $0$ 到 $n * m - 1$ 的每个整数（含两端）在网格里都恰好出现一次。 令 $i j$ 表示位于第 $i$ 行第 $j$ 列的格子。您现在需要从 $(1,1)$ 出发并前往 $(n,m)$。当您位于格子 $(i,j)$时，您可以选择走到右方的格子 $(i,j+1)$（若 $j \lt m$），也可以选择走到下方的格子 $(i+1,j)$（若 $i \lt n$）。 令 $S$ 表示路径上每个格子里的整数形成的集合，包括$a_{1,1}$ 和 $a_{n,m}$ 。令 $mex(S)$ 表示不属于S的最小非负整数。请找出一条路径以最大化 $mex(S)$，并求出这个最大的值。

输入样例

第一行输入两个整数 $n$ 和 $m$ （$1 \le n,m \le 10^6，1 \le n,m \le 10^6$）表示网格的行数和列数。 对于接下来 $n$ 行，第$i$行输入$m$个整数$a_{i,1}, a_{i,2}, a_{i,m},0 \le a_{i,j} \lt n,m$，其中 $a_{i,j}$ 表示格子 $(i,j)$ 里的整数。从 $0$ 到 $(n*m - 1)$ 的每个整数（含两端）在网格里都恰好出现一次。

输出样例

输出一行一个整数，表示最大的 $mex(S)$

样例1

输入

2 3
1 2 4
3 0 5

输出

3

样例2

输入

1 5
1 3 0 4 2

输出

5

样例解释

对于第一组样例数据，共有 $3$ 条可能的路径。 -第一条路径为 $(1,1) -> (1,2) -> (1,3) -> (2,3)$。$S = \{1,2,4,5\}$因此 $mex(S)=0$。 -第二条路径为 $(1,1) -> (1,2) -> (2,2) -> (2,3)$。$S= \{1,2,0,5\}$因此 $mex(S)=3$。 -第三条路径为 $(1,1) -> (2,1) -> (2,2) -> (2,3)$。$S= \{1,3,0,5\}$因此 $mex(S)=2$ 。 因此答案为 $3$ 。

对于第二组样例数据，只有 $1$ 条可能的路径，即 $(1,1)-> (1,2)-> (1,3)-> (1,4)-> (1,5)$ 。$S = \{1,3,0,4,2\}$ 因此 $mex(S) = 5$。

数据分布

$40\%$ 的样例，$1 \le n,m \le 100$, $n*m \le 100$。

$100 \%$ 的样例，$1 \le n,m \le 10^6$,$n*m \le 10^6$。