4308 - Path Planning

有一个 n 行 m 列的网格。网格里的每个格子都写着一个整数，其中第 i 行第 j 列的格子里写着整数 a_{i, j}。从 0 到 (n \times m - 1) 的每个整数（含两端）在网格里都恰好出现一次。

令 (i, j) 表示位于第 i 行第 j 列的格子。您现在需要从 (1, 1) 出发并前往 (n, m)。当您位于格子 (i, j) 时，您可以选择走到右方的格子 (i, j + 1)（若 j < m），也可以选择走到下方的格子 (i + 1, j)（若 i < n）。

令 \mathbb{S} 表示路径上每个格子里的整数形成的集合，包括 左上角（1，1） 和 右下角（n, m）.令 mex(\mathbb{S}) 表示不属于 \mathbb{S} 的最小非负整数。请找出一条路径以最大化 mex(\mathbb{S})，并求出这个最大的值。

第一行输入两个整数 n 和 m（1 \le n, m \le 10^6，1 \le n \times m \le 10^6）表示网格的行数和列数。

对于接下来 n 行，第 i 行输入 m 个整数。保证0 ~ n× m-1均只出现一次

保证所有数据 n \times m 之和不超过 10^6。

每组数据输出一行一个整数，表示最大的 mex(\mathbb{S})

对于第一组样例数据，共有 3 条可能的路径。

• 第一条路径为 (1, 1) \to (1, 2) \to (1, 3) \to (2, 3)。\mathbb{S} = {1, 2, 4, 5} 因此 0
• 第二条路径为 (1, 1) \to (1, 2) \to (2, 2) \to (2, 3)。\mathbb{S} = {1, 2, 0, 5} 因此3
• 第三条路径为 (1, 1) \to (2, 1) \to (2, 2) \to (2, 3)。\mathbb{S} = {1, 3, 0, 5} 因此 2

GDCPC