Maximizing the MEX on a Grid Path

You are given a grid with $n$ rows and $m$ columns. Each cell of the grid contains a unique integer from $0$ to $n \times m - 1$. The integer in the cell at row $i$ and column $j$ is denoted by $a_{i,j}$. You start at the top‐left cell $(1,1)$ and need to reach the bottom‐right cell $(n,m)$ by only moving right or down.

Let \(\mathbb{S}\) be the set of integers on your path (including the starting and ending cells). The mex of a set, denoted by \(\text{mex}(\mathbb{S})\), is defined as the smallest non-negative integer that is not present in \(\mathbb{S}\). Your task is to find a path from $(1,1)$ to $(n,m)$ such that \(\text{mex}(\mathbb{S})\) is maximized, and output this maximum possible value.

Note: Since every integer between $0$ and $n\times m-1$ appears exactly once in the grid, the maximum possible \(\text{mex}(\mathbb{S})\) is equal to the largest integer \(k\) such that all integers $0,1,2,\dots,k-1$ can be collected on some valid monotonic path starting at $(1,1)$ and ending at $(n,m)$.

inputFormat

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain $m$ integers representing the grid. The $j$-th integer in the $i$-th line is $a_{i,j}$.

outputFormat

Output a single integer which is the maximum possible value of \(\text{mex}(\mathbb{S})\) over all valid paths from $(1,1)$ to $(n,m)$.

sample

2 2
0 1
2 3

2