Maximum sum path in a matrix


Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking a path, starting at any cell of the matrix and always moving downwards or rightwards. Additionally we also have to find the number of times that this sum is achievable.

For example:
For the matrix
1 1 1
2 2 2
3 3 3
The maximum sum is 12 and it occurs only once