Chữ X may mắn

Tại Trại hè Hùng Vương lần thứ XV tổ chức tại Sơn La, học sinh được tham gia rất nhiều trò chơi thú vị. La Văn Sơn là người đầu tiên tham gia vào trò chơi "Chữ X may mắn".

Trò chơi gồm một bảng gồm $N$ hàng và $N$ cột, các hàng được đánh số từ $1$ đến $N$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $N$ từ trái sang phải. Ô giao giữa hàng $i$ và cột $j$ gọi là ô $(i,j)$ có ghi một giá trị nguyên $a_{ij}$.

Mỗi người chơi nhận được một chữ "X" có kích thước như nhau, chữ "X" gồm $2$ nét có kích thước mỗi nét bằng $K$ độ dài đường chéo các ô vuông đơn vị của bảng số ($K$ là một số nguyên dương lẻ). Người chơi sẽ đặt chữ "X" vào bảng số thỏa mãn các điều kiện sau:

• Hai nét của chữ "X" phải song song hoặc trùng với các đường chéo của bảng số.
• Chữ "X" phải nằm trọn vẹn trong bảng số.
• Giao điểm của hai nét chữ "X" phải là tâm của một ô vuông đơn vị của bảng số.

Như vậy, đặt $r=\frac{K-1}{2}$, nếu giao điểm là tâm ô $(i,j)$ thì một nét đi qua $K$ ô $(i+d,j+d)$ và nét kia đi qua $K$ ô $(i+d,j-d)$ với $d=-r,\dots ,r$; mọi ô này phải nằm trong bảng. Chữ "X" đi qua tổng cộng $2K-1$ ô (ô $(i,j)$ chung của hai nét chỉ được tính một lần).

Điểm số nhận được của người chơi bằng tổng các giá trị của các ô mà chữ "X" đi qua. Với lợi thế là người đi đầu tiên, Sơn sẽ nắn nót để nhận được số điểm lớn nhất. Sơn bắt buộc phải đặt chữ "X", nên điểm số có thể âm.

Yêu cầu: Hãy cho biết Sơn có thể đạt điểm số lớn nhất bằng bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương $N,K$ ($N\le 1000$, $K$ lẻ, $K\le N$).
• $N$ dòng sau, mỗi dòng chứa $N$ số nguyên là giá trị của các ô vuông đơn vị của bảng số đã cho, mỗi số cách nhau một khoảng trống và có giá trị tuyệt đối không lớn hơn ${10}^9$.

Dữ liệu ra

In ra một số nguyên duy nhất là điểm số lớn nhất mà Sơn có thể nhận được.

Ràng buộc

• $1\le K\le N\le 1000$, $K$ lẻ.
• $|a_{ij}|\le {10}^9$.

Subtasks

• $50\%$ số test: $K=1$.
• $25\%$ số test: $N\le 100$.
• $25\%$ số test còn lại: $N\le 1000$.

Ví dụ