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ố.

Điểm số nhận được của người chơi bằng tổng số 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.

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?

Input

• Dòng 1: 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~.

Output

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