I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in the $i$-th row from interval $[a, b]$, then I have to also take the interval $[\max(1, a - 1), \min(b + 1, M)]$ in the $i + 1$-th row. In other words, if I use all of $A[i][a], \dots, A[i][b]$, then I also have to use the elements $A[i+1][\max (1, a-1)],\dots ,A[i+1][\min (b+1, M)]$.
I can't think of any algorithm for this. I don't even have any idea how to brute-force it. Could someone please help me solve that? I think the optimal solution should have $O(N \cdot M)$ complexity or something like that.
Example input: $N=4$, $M=7$, and $$A = \left(\begin{matrix} &-1 &4 &-6 &-1 &-2 &-5 &10 \\ &5 &-7 &2 &1 &-9 &-13 &2 \\ &2 &4 &-10 &3 &1 &2 &6 \\ &3 &2 &7 &1 &-7 &4 &5 \end{matrix}\right). $$
For this problem instance, the maximal sum is $40$. This can be achieved by taking the 5 in the first column, the 3 in the fourth column, the 1 in the fifth column and the 2 in the last column as the summits of the triangles.