402366: GYM100738 L Plantations

You're given a matrix with N lines and N columns. Let's define sum of a square submatrix as sum of all numbers from its main diagonal and from its secondary diagonal. Note that the intersection of the diagonals needs to be added only once to the sum. For example, for the matrix

1 2 3

4 5 6

7 8 9

the sum is 1+5+9+7+3 = 25.

Find the largest square submatrix such as its sum is smaller or equal to W.

The first line contains T, the number of tests (T ≤ 20). Next T lines describe the test cases. On first line of each test there are given two numbers N and W (1 ≤ N ≤ 1000, W is a 32-bit number (can be stored in int type)).

Next N lines contain N elements, describing the element of the matrix. All numbers are positive, up to int maximum value.

Outout the answer for each of the T test cases

1
3 5
1 1 1
1 1 1
1 1 1

3

Note: The time limit of this problem is unusual. Please check it.