402366: GYM100738 L Plantations

Memory Limit:64 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Plantationstime limit per test3 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

Outout the answer for each of the T test cases

ExamplesInput
1
3 5
1 1 1
1 1 1
1 1 1
Output
3
Note

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

加入题单

上一题 下一题 算法标签: