Find a maximum sum in matrix, subject to special constraint
This can be solved in $O(NM)$ time using dynamic programming.

Given any solution, let $s$ denote the smallest index $s$ such that $a[s][1]$ is selected.  (It follows that $a[1][1],\dots,a[s-1][1]$ are not selected and that $a[s][1],\dots,a[N][1]$ are selected.)  This partitions solutions based on the value of $s$, i.e., based on which entries from the first column are selected in that solution.  There are only $N$ possible values for $s$.

Now define $f(s,t)$ to be the largest sum that is possible by selecting some entries from the submatrix $a[1..N][t..M]$, subject to the restriction that you choose all of $a[s..N][t]$ and don't choose any of $a[1..s-1][t]$.  You can easily find a recurrence relation that expresses $f(s,t)$ in terms of a few values of the form $f(s',t+1)$.  This immediately yields a simple dynamic programming algorithm with running time $O(NM)$.