Để chào đón kỳ thi Olympic Tin học Quốc tế năm 2007, thành phố Zagreb dự định xây dựng một trung tâm thương mại lớn ở ngoại ô. Khu đất dự kiến được chia thành một lưới gồm \(m\) cột theo chiều ngang và \(n\) hàng theo chiều dọc. Chẳng hạn, với \(m=10\) và \(n=7\), khu đất có \(10\) cột và \(7\) hàng ô vuông.

Thành phố phải chọn một vùng hình chữ nhật rộng \(a\) ô, cao \(b\) ô để xây trung tâm thương mại. Một số ô đã có người sinh sống nên không thể sử dụng. Nếu một vùng hình chữ nhật có kích thước yêu cầu không chứa ô nào có người ở, thành phố có thể mua tất cả các ô trong vùng đó để xây dựng.

Do ngân sách có hạn, thành phố muốn tổng chi phí mua đất nhỏ nhất. Cho kích thước khu đất, kích thước trung tâm thương mại và thông tin của từng ô, hãy tính chi phí nhỏ nhất cần bỏ ra.

Ký hiệu \((i,j)\) là ô ở cột thứ \(i\) từ trái sang và hàng thứ \(j\) từ trên xuống. Chiều ngang của vùng được chọn phải là \(a\), chiều dọc phải là \(b\).

Giới hạn thời gian là \(6\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(m,n\).
• Dòng thứ hai chứa hai số nguyên \(a,b\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(j\) chứa \(m\) số nguyên \(c_{1,j},c_{2,j},\ldots,c_{m,j}\). Nếu \(c_{i,j}=-1\), ô \((i,j)\) đã có người ở. Nếu không, \(c_{i,j}\) là chi phí mua ô đó.

Các số trên cùng một dòng được ngăn cách bởi dấu cách. Dữ liệu bảo đảm luôn có thể xây trung tâm thương mại.

Kích thước dữ liệu vào có thể lớn. Cần chú ý tốc độ đọc dữ liệu; trong C++, có thể dùng fscanf khi cần thiết.

Dữ liệu ra

Ghi ra đầu ra chuẩn chi phí mua đất nhỏ nhất để xây trung tâm thương mại.

Ràng buộc

• \(1 \le m,n \le 1000\).
• \(1 \le a,b \le 1000\).
• \(-1 \le c_{i,j} \le 100\) với mọi \(1 \le i \le m\), \(1 \le j \le n\).
• Tồn tại ít nhất một vùng hợp lệ rộng \(a\) ô và cao \(b\) ô.

Phân nhóm

Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.

1. Bộ dữ liệu 1: \(20\) điểm.
2. Bộ dữ liệu 2: \(20\) điểm.
3. Bộ dữ liệu 3: \(20\) điểm.
4. Bộ dữ liệu 4: \(20\) điểm.
5. Bộ dữ liệu 5: \(20\) điểm.

Ví dụ

7 6
3 2
26 29 84 15 -1 1 71
45 14 38 91 62 77 35
68 -1 -1 90 63 56 70
31 2 4 74 72 41 90
100 26 21 -1 44 72 60
71 4 40 93 48 -1 50

184