Đó là một ngày hè nóng nực và cô bò Bessie cảm thấy khá lười biếng. Cô muốn chọn một vị trí trong cánh đồng để có thể tiếp cận nhiều cỏ ngon nhất có thể mà chỉ phải đi một quãng ngắn.

Cánh đồng nơi Bessie sống được mô tả bởi một lưới gồm \(N \times N\) ô vuông (\(1 \le N \le 400\)). Ô ở hàng \(r\), cột \(c\) (\(1 \le r,c \le N\)) chứa \(G(r,c)\) đơn vị cỏ (\(0 \le G(r,c) \le 1\,000\)). Từ ô xuất phát trên lưới, Bessie chỉ sẵn lòng đi nhiều nhất \(K\) bước (\(0 \le K \le 2N\)). Mỗi bước đưa cô đến ô nằm ngay phía bắc, nam, đông hoặc tây của vị trí hiện tại.

Ví dụ, giả sử lưới như sau, trong đó (B) biểu thị vị trí ban đầu của Bessie (ở đây là hàng \(3\), cột \(3\)):

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

Nếu \(K=2\), Bessie chỉ có thể đến các vị trí được đánh dấu *.

Hãy giúp Bessie xác định lượng cỏ lớn nhất mà cô có thể tiếp cận nếu chọn vị trí ban đầu tối ưu trên lưới.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(r\) chứa \(N\) số nguyên mô tả hàng \(r\) của lưới.

Ràng buộc

• \(1 \le N \le 400\).
• \(0 \le K \le 2N\).
• \(0 \le G(r,c) \le 1\,000\).

Dữ liệu ra

In ra lượng cỏ lớn nhất Bessie có thể tiếp cận nếu chọn vị trí ban đầu tối ưu, tức là vị trí cho phép cô tiếp cận nhiều cỏ nhất.

Ví dụ

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

342

Nguồn

USACO 2014 March Contest, Silver — The Lazy Cow

Tác giả: Brian Dean, 2014.