Xsquare and A Gaming Matrix

★★★★★

4.5

2 votes

Algorithms, Dynamic Programming, Open, Approved, Hard

Details

Submissions

Discussion

Editorial

Problem

Xsquare loves to play games very much. Today, he has a special square matrix M of size N x N containing both non-negative as well as negative integers which he calls a Gaming Matrix. Rows and columns of his Gaming Matrix are numbered from 1 to N.

In one move, he performs following operations :

He can select any out of the four available corner cells of his gaming matrix.
Add value of the selected cell to his score.
Discard the selected cell.
If N > 1, Replace existing gaming matrix with any of available square matrix of size N-1.
NOTE : For a gaming matrix of size N x N where N > 1, Xsquare can select any square matrix of size N-1 as his new gaming matrix which does not contains the discarded cell.
If N == 1, Game is over.

Refer to the figure for better understanding of a gaming move.

Let us consider the following Gaming Matrix of size 3 x 3.

enter image description here

During his first move, Xsquare selected the highlighted cell and added its value to his score.
Xsquare then discarded this selected cell.

enter image description here

Xsquare selected the highlighted square matrix as new Gaming Matrix ( offcourse it is of size N-1 i.e 2 x 2 ).
During his second move, Xsquare selected the highlighted cell and added its value to his score.
Xsquare then discarded this selected cell.

enter image description here

Finally during his third move, Xsquare selected the highlighted cell i.e cell with value 6.
As N == 1, Game is over.

This way Xsquare managed to get a score 24 which is maximum possible score .

Note that Xsquare cannot leave the game in between till it is over.

Your task is very very simple. Given a Gaming Matrix of size N x N. Find the maximum possible score that can be achieved following the above moves .

Input

First line of input contains a single integer T denoting the number of test cases. First line of each test case contains a single integer N denoting the size of the matrix M. Next N line of each test cases contains N space separated integers where j^th element in the i^th line denotes the value of the cell M[i][j].