Cho ma trận ~a~ gồm ~m~ hàng và ~n~ cột, các hàng đánh số từ trên xuống dưới, các cột đánh số từ trái sang phải. Ô ở hàng ~i~ cột ~j~ có giá trị nguyên ~a_{i,j}~ ~(|a_{i,j}| \le 10^9)~. Với mỗi ma trận vuông ~k \times k~, định nghĩa nửa dưới của nó là tất cả các ô nằm trên đường chéo chính và dưới đường chéo chính trái trên - phải dưới.

Yêu cầu: Tìm hình vuông cỡ ~k \times k~ sao cho tổng các số ở nửa dưới của nó đạt giá trị lớn nhất.

Input

• Dòng đầu ghi ba số ~m, n, k~ ~(m, n \le 2000, k \le \min(m,n))~;

• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số là ma trận ~a~.

Output

Ghi một số nguyên duy nhất là kết quả tìm được.

Scoring

Sample Input 1

3 4 2
1 2 1 1
2 1 3 4
1 2 1 2

Sample Output 1

8