Quan sát động vật

Một khu rừng được chia thành $m$ khu vực, đánh số từ $1$ đến $m$. Người ta muốn quan sát động vật trong khu rừng trong $n$ ngày liên tiếp (ngày $1$ đến ngày $n$) bằng cách sử dụng hai camera:

• Vào các ngày lẻ ($1$, $3$, $5$, $\dots$), đặt camera đỏ; camera này quay trong $2$ ngày liên tiếp.
• Vào các ngày chẵn ($2$, $4$, $6$, $\dots$), đặt camera xanh; camera này quay trong $2$ ngày liên tiếp.
• Nếu bắt đầu đặt camera vào ngày $n$ thì camera đó chỉ quay được $1$ ngày.

Mỗi camera có thể quan sát $k$ khu vực liên tiếp. Chẳng hạn, với $m=5$ và $k=3$, có thể đặt camera để quan sát một trong ba đoạn khu vực (kéo dài $2$ ngày liên tiếp): $[1,3]$, $[2,4]$ hoặc $[3,5]$.

Bạn được biết trước số lượng động vật xuất hiện trong mỗi khu vực trong mỗi ngày. Hãy chọn vị trí đặt hai camera cho $n$ ngày sao cho tổng số động vật quan sát được là lớn nhất. Nếu cùng một khu vực trong cùng một ngày được cả hai camera quan sát thì số động vật ở đó chỉ được tính $1$ lần.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$ — số ngày, số khu vực, và độ rộng của camera.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên. Số thứ $j$ trên dòng thứ $i+1$ là số động vật có mặt tại khu vực $j$ trong ngày $i$.

Dữ liệu ra

• Một số nguyên duy nhất: số động vật lớn nhất có thể quan sát được.

Ràng buộc

• $1\le n\le 50$
• $1\le m\le 2·{10}^4$
• $1\le k\le m$
• Số động vật ở mỗi ô nằm trong khoảng $[0,1000]$.

Ví dụ