Lazy Cow Graze Optimization

Bessie the cow is very lazy. On a hot summer day, she wants to locate herself in her field so that she can reach as much delicious grass as possible within a limited number of steps.

The field is given as an \(N \times N\) grid, where the cell at row \(r\) and column \(c\) contains \(G(r,c)\) units of grass. Bessie is willing to move at most \(K\) steps from her chosen cell. Each step moves her one cell in one of the four cardinal directions (north, south, east, or west). A cell \((i,j)\) is reachable from cell \((r,c)\) if and only if

[ |i-r|+|j-c| \leq K. ]

Your task is to help Bessie choose the best starting cell so that the sum of grass units in the reachable cells is maximized.

Input Constraints:

• \(1 \leq N \leq 400\)
• \(0 \leq G(r,c) \leq 1000\)
• \(0 \leq K \leq 2N\)

inputFormat

The first line contains two integers \(N\) and \(K\). The next \(N\) lines each contain \(N\) integers. The \(j\)-th integer in the \(i\)-th line represents \(G(i,j)\), the amount of grass at that cell.

Format:

N K
G(1,1) G(1,2) ... G(1,N)
G(2,1) G(2,2) ... G(2,N)
...
G(N,1) G(N,2) ... G(N,N)

outputFormat

Output a single integer: the maximum total amount of grass Bessie can reach from the best starting position.

sample

3 1
1 2 3
4 5 6
7 8 9

25