Ecology Preserve

Time limit2sMemory limit512 MB

Summary

Given an N by N grid of tree counts, pick a connected set of exactly M cells (M at most 10) maximizing the total tree count.

Level: Hard8 of 10
Topics: Dynamic programming, DFS, Implementation, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1

Input

5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7

Expected output

Example 2
Input
```
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1
```
Expected output
```
72
```