📖 Bài giảng & lời giải: đây là Bài tập 2 trong bài giảng Chuyên đề nhập môn 9: Cộng dồn 2 chiều trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cánh đồng là một bảng gồm $n$ hàng, $m$ cột; ô ở hàng $i$, cột $j$ cho sản lượng $a_{ij}$ (số âm nghĩa là phải bỏ tiền cải tạo). Cần chọn một mảnh đất hình vuông kích thước $k \times k$ (gồm $k$ hàng liên tiếp và $k$ cột liên tiếp, nằm trọn trong cánh đồng) có tổng sản lượng lớn nhất.

In ra tổng đó và toạ độ góc trên trái (hàng, cột) của mảnh đất. Nếu có nhiều mảnh đất cùng đạt tổng lớn nhất, chọn mảnh có hàng góc trên trái nhỏ nhất; nếu vẫn còn nhiều, chọn mảnh có cột nhỏ nhất.

Dữ liệu vào

• Dòng 1: ba số nguyên $n, m, k$ ($1 \le n, m \le 1000$, $1 \le k \le \min(n, m)$).
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ số nguyên $a_{ij}$ ($|a_{ij}| \le 10^9$).

Kết quả

• Dòng 1: tổng sản lượng lớn nhất.
• Dòng 2: hai số nguyên là hàng và cột của góc trên trái mảnh đất được chọn, cách nhau một dấu cách.

Sample Input

4 5 2
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4

Sample Output

28
3 4