The Lazy Cow

Time limit1sMemory limit128 MB

Summary

Choose the cell whose Manhattan diamond of radius K holds the most grass and output that sum.

Level: Medium5 of 10
Topics: Prefix sum, Matrix
Solved: No attempts yet

Problem

On a hot summer day, Bessie the cow feels lazy. She wants to pick a starting cell in her field so that she can reach as much tasty grass as possible within a short walk.

The field is an $N \times N$ grid ( $1 \le N \le 400$ ). Cell $(r,c)$ ( $1 \le r,c \le N$ ) contains $G(r,c)$ units of grass ( $0 \le G(r,c) \le 1000$ ). From her starting cell, Bessie takes at most $K$ steps ( $0 \le K \le 2N$ ). Each step moves her one cell north, south, east, or west.

Choose the best starting cell. Output the maximum total grass she can reach within $K$ steps.

Input

Line 1: integers $N$ and $K$ .
Lines 2 through $N+1$ : $N$ integers per line, row $r$ of the grid.

Output

Line 1: the maximum total grass reachable within $K$ steps from the best starting cell.

Hint

Try every starting cell and sum grass reachable within $K$ steps.

Examples5

Example 1

Input

5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

Expected output

Example 2
Input
```
1 0
137
```
Expected output
```
137
```

Example 3

Input

3 1
978 883 970
869 57 93
86 369 855

Expected output

Example 4

Input

4 3
243 606 557 133
378 937 618 485
640 594 67 620
13 930 857 480

Expected output

Example 5

Input

6 2
241 310 105 738 405 490
158 92 68 20 411 562
939 296 819 783 60 227
532 549 368 283 798 176
846 108 268 219 965 949
26 848 656 826 266 819

Expected output