"Two Goats, frisking gayly on the rocky steeps of a mountain valley, chanced to meet, one on each side of a deep chasm through which poured a mighty mountain torrent. The trunk of a fallen tree formed the only means of crossing the chasm, and on this not even two squirrels could have passed each other in safety. The narrow path would have made the bravest tremble. Not so our Goats. Their pride would not permit either to stand aside for the other.

One set her foot on the log. The other did likewise. In the middle they met horn to horn. Neither would give way, and so they both fell, to be swept away by the roaring torrent below."

"The two goats story", Aesop's Fables (source: https://fablesofaesop.com/two-goats.html)

Mẫu truyện trên kể về hai chú dê cùng đi qua một chiếc cầu chật hẹp được hình thành từ một cái thân cây đã ngã. Với lòng tự tôn vô cùng to lớn, không một con dê nào chịu nhường con còn lại. Kết quả thì hẵn chúng ta ai cũng đã biết: chúng dùng sừng húc nhau trên cây cầu chênh vênh, khiến cả hai cùng ngả xuống dòng sông đang chảy siết.

Tuy nhiên, hôm nay, chúng ta sẽ hình dung lại câu truyện trên theo một cách hòa thuận và cho nó một cái kết có hậu hơn. Cụ thể, hai chú dê quyết định sử dụng phép thuật để xây một chiếc cầu cho cả hai cùng đi qua.

Nếu hình dung khoảng không gian giữa hai vách núi thành một bảng hai chiều có ~n~ dòng và ~m~ cột, với cột thứ ~1~ và thứ ~m~ là hai vách núi, ta có bảng ~a~ kích thước ~n \times m~ sao cho ~a_{i, j}~ mô tả chi phí xây dựng cầu tại vị trí giao giữa dòng thứ ~i~ và cột thứ ~j~. Nhiệm vụ của hai chú dê là như sau:

• Chọn ra ~k~ dòng liên tiếp làm vùng xây cầu.
• Chọn một dòng bất kỳ rồi dùng phép thuật để gán toàn bộ các giá trị ~a_{i, j}~ trên dòng đó bằng ~0~.
• Với mỗi dòng ~i~ trong số các dòng đã được chọn, hai chú dê cần kết nối hai vách núi như sau: Chọn một tập các ô trên dòng ~i~ sao cho ô ~(i, 1)~ và ~(i, m)~ luôn được chọn, hơn nữa, hai ô liên tiếp (chỉ tính trên dòng ~i~) cách nhau không quá ~d~ ô. Ví dụ, giả sử hai chú dê chọn các cột ~j_1, j_2, j_3, \dots, j_r~ trên dòng ~i~ để xây cầu, ta cần đảm bảo ~j_1 = 1, j_r = m~ và:

$$ \max_{2 \leq i \leq r} j_i - j_{i-1} \leq d $$

Trong các cách chọn ô để xây cầu thỏa mãn cả ~3~ điều kiện trên, hãy giúp hai chú dê chọn ra các xây cầu có tổng chi phí nhỏ nhất.

Input

Nhập dữ liệu qua tập tin văn bản ENGLISH.INP:

• Dòng đầu tiên của dữ liệu vào chứa bốn số nguyên ~n, m, k, d~ (với ~k \leq n~ và ~d \leq m~) lần lượt là kích thước của khoảng không gian cần xét giữa hai vách núi, số dòng cần chọn và khoảng cách tối đa giữa hai ô trên cùng một dòng.
• Trên ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, a_{i, 3}, \dots, a_{i, m}~ mô tả chi phí xây cầu cho các ô trên bảng.

Output

Xuất dữ liệu qua tập tin văn bản ENGLISH.OUT:

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để xây cầu.

Ràng buộc

Ví dụ

Input mẫu

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

Output mẫu

15

Giải thích

• Đầu tiên, ta chọn dòng ~1, 2, 3~ để xây cầu.
• Sau đó, dùng phép thuật để gán toàn bộ các giá trị trên dòng thứ hai thành ~0~.
• Cuối cùng, ta chọn các ô như sau:
  • Ở dòng đầu tiên: Chọn các ô ~(1, 1)~, ~(1, 2)~ và ~(1, 4)~ với chi phí ~4 + 1 + 2 = 7~.
  • Ở dòng thứ hai: Chọn các ô ~(2, 1)~, ~(2, 2)~ và ~(2, 4)~ với chi phí ~0~ do đã sử dụng phép thuật.
  • Ở dòng thứ ba: Chọn các ô ~(3, 1)~, ~(3, 3)~ và ~(3, 4)~ với chi phí ~3 + 3 + 2 = 8~.
• Tổng chi phí cuối cùng là ~15~, có thể thấy, đây là phương án tối ưu.