Chính phủ Siruseri quyết định đấu giá đất tại tỉnh Navalur giàu dầu mỏ cho các nhà thầu tư nhân xây dựng giếng dầu. Toàn bộ khu vực được đấu giá được chia thành một lưới hình chữ nhật gồm \(M \times N\) ô đất nhỏ.

Cơ quan Khảo sát Địa chất Siruseri có dữ liệu về trữ lượng dầu ước tính ở Navalur. Dữ liệu này được công bố dưới dạng một lưới \(M \times N\) số nguyên không âm, cho biết trữ lượng ước tính trong từng ô đất.

Để ngăn chặn độc quyền, chính phủ quy định mỗi nhà thầu chỉ được đấu giá một khối vuông gồm \(K \times K\) ô đất liền nhau. Liên minh dầu mỏ AoE gồm ba nhà thầu thông đồng với nhau, muốn chọn ba khối không có ô đất chung sao cho tổng trữ lượng dầu trong các khối được chọn là lớn nhất.

AoE thuê bạn viết chương trình xác định tổng trữ lượng dầu ước tính lớn nhất mà họ có thể giành được.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(M\), \(N\) và \(K\), trong đó \(M\), \(N\) lần lượt là số hàng và số cột của lưới, còn \(K\) là độ dài cạnh của khối vuông được phép đấu giá.

Trong \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên không âm mô tả trữ lượng dầu ước tính ở các ô đất trên một hàng.

Dữ liệu ra

In một dòng chứa một số nguyên duy nhất: tổng trữ lượng dầu ước tính lớn nhất mà liên minh AoE có thể giành được.

Ràng buộc

• \(1 \le M, N \le 1500\).
• \(1 \le K \le \min(M,N)\).
• Trữ lượng dầu ước tính trong mỗi ô là một số nguyên từ \(0\) đến \(500\).
• Luôn có thể chọn ít nhất ba khối \(K \times K\) không có ô đất chung.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

208

Nguồn

Asia-Pacific Informatics Olympiad 2009 — Oil (Digging for Oil), đề tiếng Anh phiên bản 1.3.