Field

You are given a field which is a square table N x N filled with non-negative integers. Write a program field that calculates the minimum number M, such that all squares of size M x M that cover the whole number of cells in the field have their sum greater than or equal to K. The boundary of the square may lie on the boundary of the field.

The first line of the standard input contains two integers separated by a space - N and K. The next N lines of the input contain N integers each, which represent the elements of the field.

The program should send to the standard output one line, containing only one integer equal to the found minimum value of M or -1, if no such value exists.

• 1 ≤ N ≤ 5000
• 0 ≤ each element in the field ≤ 50
• 1 ≤ K ≤ 2⋅109

For M=1 the 1x1 square:

2

has a sum of just 2 < 10.

For M=2 the 2x2 square:

0 7
0 2

has a sum of 9 < 10. For M=3 each 3x3 square has a sum ≥ 10.

Thus M=3 is the minimal M such that each square of size M x M has a sum of at least 10.