Tam giác

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 (đường chéo trái trên, phải dưới). Nói cách khác, với hình vuông có ô trái trên là $(i,j)$, nửa dưới gồm các ô $(i+r,j+c)$ với $0\le c\le r\le k-1$.

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

Dữ liệu vào

• Dòng đầu ghi ba số nguyên $m,n,k$ ($1\le m,n\le 2000$, $1\le k\le min(m,n)$).
• $m$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên là một hàng của ma trận $a$.

Dữ liệu ra

Ghi một số nguyên duy nhất là tổng lớn nhất tìm được.

Ràng buộc

• $1\le m,n\le 2000$.
• $1\le k\le min(m,n)$.
• $|a_{i,j}|\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $m,n\le 50$.
• Subtask 2 ($40\%$ số điểm): $50<m,n\le 500$.
• Subtask 3 ($30\%$ số điểm): $500<m,n\le 2000$.

Ví dụ