Mô tả và yêu cầu

VOI 11 Bài 1 - Phần thưởng

Time Limit: 0.6s Memory Limit: 512M

Tuấn là người chiến thắng trong một cuộc thi "tìm hiểu kiến thức vũ trụ" và được nhận các phần
thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông 𝑛×𝑛 có
dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến 𝑛, từ trên
xuống dưới và các cột của bảng được đánh số từ 1 đến 𝑛, từ trái qua phải. Ô nằm trên giao của
dòng 𝑖 và cột 𝑗 được gọi là ô (𝑖,𝑗) và trên ô đó chứa một món quà có giá trị là
𝑎[𝑖,𝑗](1≤𝑖,𝑗≤𝑛).

Đề nhận phần thưởng, Tuấn được phép chọn một hình vuông kích thước 𝑘×𝑘 chiếm trọn trong
một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó.

Dữ liệu vào

Dòng thứ nhất chứa hai sô nguyên dương 𝑛,𝑘(𝑛≤1 0 0 0,𝑛≤𝑘≤𝑛).
3
Dòng thứ 𝑖 trong số 𝑛 dòng tiếp theo chứa 𝑛 số nguyên dương, số thứ 𝑗 là
𝑎[𝑖,𝑗](𝑎[𝑖,𝑗]≤1 0 0 0).

Dữ liệu ra

Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận
được.

Giới hạn và chấm điểm

50% số test ứng với 50% số điểm của bài có 𝑛≤1 0 0.

Sample Input

4 3
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14

Sample Output

86