Ecology Preserve

The kingdom of Polyminogonia recently passed an ecology law. Every farm has to leave a fixed fraction of its area as a preserved region and keep as many trees as possible inside it. Wild animals have to move freely inside that region, so the preserved region must be connected.

A farm in Polyminogonia is always a grid of $N \times N$ squares of one hectare each. The figure shows a farm with $N = 5$. The preserved region must cover exactly $M$ squares, and in the figure $M = 6$. The region must be orthogonally connected: for any two preserved squares, you can get from one to the other by up, down, left and right moves that only step on preserved squares. The region that is not preserved may be disconnected.

The farmers know how many trees stand in each square. Write a program that computes the largest number of trees a preserved region of $M$ squares can hold. On the farm in the figure, 377 trees can be preserved.

The first line contains two integers $N$ and $M$ ($2 \le N \le 50$, $1 \le M \le 10$, $M \le N^2$). Each of the next $N$ lines contains $N$ integers, the number of trees in each square of the farm. Every value is between 1 and 1000.

Print one line with a single integer, the largest number of trees that can be preserved.