E. MAHATAN - Khoảng cách MAHATAN

Cho lưới ô vuông kích thước ô vuông , các hàng đánh số từ đến từ trên xuống dưới và các cột đánh số từ đến từ trái qua phải. Ô vuông nằm ở hàng và cột có chứa số nguyên và được ký hiệu là . Khoảng cách Mahatan giữa hai ô và được tính bởi công thức .

Yêu cầu: Cho trước số , hãy tìm ô mà tổng giá trị của các ô trong bảng có khoảng cách đến không lớn hơn là lớn nhất. Bạn cũng chỉ cần in ra giá trị lớn nhất này.

Ví dụ dưới đây, khi Thì ô là ô phải tìm với các ô màu xám có khoảng cách không lớn hơn :

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên dương ;
• dòng tiếp theo, dòng thứ ghi số nguyên, số thứ là .

Dữ liệu ra:

• Một số nguyên duy nhất là giá trị tổng lớn nhất tìm được.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

342