As Pal have commented, this is a question in dynamic programming. I will now propose the solution using dynamic programming to the question, *but I highly recommend trying it on your own first, and checking this later.*

**The algorithm:**

- Create a new empty matrix $V$ of size N by N
- for $1 le i le N:$
- for $1 le j le N:$
- Set $V(i, j) = M(i,j) + max(V(i-1, j), V(i, j-1))$ (note that $V(-1,j) = V(i,-1) = 0$)

- for $1 le j le N:$
- Find $m = max_i,_j(V(i,j))$
- Count the number of times we see $m$ in $V$
- You can return the maximum sum $m$ and the number of times it occurs (as you have counted it)

**Complexity:**

The algorithm takes $O(N^2)$ **time** (which is $O(k)$ if we let $k$ be the input size) since it calculates a new matrix of size N by N, doing $O(1)$ operations per cell in it.

Notive that the algorithm’s **space** complexity is **also** $O(N^2)$ as we were required to create a whole new matrix.