Write a C program to get a matrix A of size 𝑁 × 𝑁. Let B be a submatrix of A with size 𝑀 × 𝑀 is a contiguous block of 𝑀 × 𝑀 elements of A in which case there must be integers r and c such that 𝐵[ 𝑖][ 𝑗] = 𝐴[𝑟 + 𝑖 − 1][𝑐 + 𝑗 − 1] ∀ 1 ≤ 𝑖, 𝑗 ≤ 𝑀.

Your task here is to find the maximum trace of a square submatrix of A.

(Hint: The trace of a matrix is defined as the sum of all elements on the main diagonal of the matrix [an element lies on the main diagonal if its row index and column index are equal].)

Constraints: ● 1 ≤ 𝑁 ≤ 100 ● 1 ≤ 𝐴[ 𝑖][ 𝑗] ≤ 100 ∀ 0 ≤ 𝑖, 𝑗 ≤ 𝑁

Example for the problem understanding:

MATRIX A WITH N 3

1 2 5

6 3 4

2 7 1

The submatrix with the largest trace is:

6 3

2 7

with trace = 6+7 = 13. This submatrix is obtained for r=2, c=1 and M=2

Test Cases:

Input 1

3

1 2 5

6 3 4

2 7 1

Output 1

13

Input 2

1

99

Output 2

99

Input 3

2

11 10

11 12

Output 3

23