Time: 1h 15m

Problem Statement

A chessboard of size N * M (i.e. N rows and M columns) is given. Each
field of the chessboard can be indexed using a pair of integers (P, Q)
where 0 <= P < N and 0 <= Q < M.

On each field of the chessboard there lies a number of rice grains. A
pawn is initially located at field (0, 0). It can perform two kinds of
moves:
- move from field (P, Q) to field (P+1, Q), or
- move from field (P, Q) to field (P, Q+1).

After N + M - 2 moves the pawn will arrive at field (N-1, M-1). During its 
movement through the chessboard it collects all the rice grains from the 
fields it stands on.

Write a function

            class Test { public int solution(int[][] A); }

that given a matrix of size N * M describing the number of rice grains
lying on each field of a N * M chessboard returns the maximal number of
rice grains a pawn can collect while moving from the field (0, 0) to the
field (N-1, M-1) in the manner specified above. Assume that . Assume that
each element of the matrix is a non-negative integer not exceeding 200.

For example, given matrix A such that 

A[0][0]=2   A[0][1]=2   A[0][2]=3   A[0][3]=0 
A[1][0]=0   A[1][1]=3   A[1][2]=1   A[1][3]=1 
A[2][0]=1   A[2][1]=2   A[2][2]=2   A[2][3]=1 
A[3][0]=4   A[3][1]=1   A[3][2]=2   A[3][3]=2

the function should return 15.

One of the paths that the pawn can take : A[0][0], A[0][1], A[1][1],
A[2][1], A[2][2], A[3][2], A[3][3]

Following this path the pawn will collect A[0][0] + A[0][1] + A[1][1] +
A[2][1] + A[2][2] + A[3][2] + A[3][3] = 2 + 2 + 3 + 2 + 2 + 2 + 2 = 15
rice grains. There is no path the pawn can take to collect more than 15
rice grains.

Assume that:
- N and M are integers in the range [0...1000]
- each element of matrix A is an integer within the range [0...200]

Complexity:
- expected worst-case time complexitiy is O(N*M)
- expected worst-case space complexitiy is O(N+M)