Grid Beauty

You are given a grid of size $N \times M$ containing all integers from $1$ to $N \times M$, each exactly once. The grid is represented as $a_{i,j}$ for $1 \le i \le N$ and $1 \le j \le M$, where $i$ denotes the row index and $j$ denotes the column index. Define the **beauty** of the grid as the maximum integer $X$ ($1 \le X \le N*M+1$) such that it is possible to sort the grid into the followin