The Lazy Cow

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.

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

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

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