Worthy Matrix

Chef found a matrix $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$), where for each row $r$ and column $c$, the cell in row $r$ and column $c$ (denoted by $(r,c)$) contains an integer $A_{r,c}$. This matrix has two interesting properties: - The integers in each row form a non-decreasing sequence, i.e. for each valid $i$, $A_{i,1} \leq A_{i,2} \leq \ldots \l