By Guilherme Albuquerque Pinto Brazil
The kingdom of Polyminogonia recently passed an ecological law that obligates every farm in the kingdom to preserve the maximum number of trees possible in a fixed percentage of the area of the farm. In addition, to allow wild animals to move freely, the preserved area must be connected. The farms in Polyminogonia are always a grid of N × N squares, one hectare each. The figure illustrates one farm, for N = 5. The preserved area should cover exactly M squares. In the example, M = 6. It should be orthogonally connected. That is, it must be possible to move between any two preserved squares making only orthogonal moves between preserved squares. The area not preserved may or may not be connected.
The farmers know the number of trees inside each square, and you have to write a program that computes the maximum number of trees that can be preserved with an area of M squares. In the example, it is possible to preserve 377 trees!
The input contains several test cases. The first line of a test case contains two integers N and M(2 ≤ N ≤ 50, 1 ≤ M ≤ 10). The next N lines contain, each one, N integers with values between 1 and 1000, representing the number of trees inside each square of the farm.
For each test case in the input your program should output one line containing one integer, the maximum number of trees that can be preserved, with the given restrictions.
|Sample Input||Sample Output|
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1