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 the matrix
1 1 1
2 2 2
3 3 3
The maximum sum is 12 and it occurs only once