Tại Zagreb, thủ đô của Croatia, để chào mừng sự kiện IOI 2007 được tổ chức, người ta quyết định xây dựng một trung tâm thương mại lớn ở vùng ngoại ô. Khu đất dự kiến để xây dựng trung tâm thương mại được chia thành một lưới gồm $m$ ô theo chiều ngang và $n$ ô theo chiều dọc như hình vẽ dưới đây.

Thành phố Zagreb quyết định chọn một vùng hình chữ nhật gồm $a$ ô theo chiều ngang và $b$ ô theo chiều dọc từ khu đất dự kiến để xây dựng trung tâm thương mại tại đó. Tuy nhiên, một số ô trong khu đất dự kiến đã có người sinh sống, và không thể xây dựng trung tâm thương mại trên phần đất đó. Nếu bên trong vùng hình chữ nhật gồm $a$ ô theo chiều ngang và $b$ ô theo chiều dọc không có ô nào có người sinh sống, trung tâm thương mại có thể được xây dựng bằng cách mua lại toàn bộ các ô trong vùng hình chữ nhật đó.

Vì lý do tài chính của thành phố Zagreb, chi phí thu hồi đất cần phải được giảm thiểu càng nhiều càng tốt. Để lập dự toán ngân sách, cần phải nhanh chóng tính toán chi phí thu hồi đất phục vụ việc xây dựng trung tâm thương mại. Do đó, thành phố Zagreb quyết định nhờ bạn, một ứng cử viên đại diện cho IOI 2007, viết một chương trình cho mục đích này.

Cho biết kích thước của khu đất dự kiến, kích thước của trung tâm thương mại, cùng với thông tin ở mỗi ô xem có người sinh sống tại đó hay không và nếu không có người sinh sống thì chi phí cần thiết để mua lại ô đó là bao nhiêu, hãy viết chương trình tìm giá trị nhỏ nhất của chi phí thu hồi đất cần thiết để xây dựng trung tâm thương mại.

Trong phần dưới đây, ô ở cột thứ $i$ tính từ bên trái và hàng thứ $j$ tính từ trên xuống của khu đất dự kiến được ký hiệu là $(i, j)$.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào mall.in chứa hai số nguyên $m, n$ ($1 \le m, n \le 1000$) cách nhau bởi dấu cách. Điều này biểu thị kích thước của khu đất dự kiến là $m$ ô theo chiều ngang và $n$ ô theo chiều dọc.

Dòng thứ hai chứa hai số nguyên $a, b$ ($1 \le a, b \le 1000$) cách nhau bởi dấu cách. Điều này biểu thị kích thước của trung tâm thương mại là $a$ ô theo chiều ngang và $b$ ô theo chiều dọc.

$n$ dòng tiếp theo (từ dòng thứ $3$ đến dòng thứ $n + 2$) ghi thông tin của từng ô trong khu đất dự kiến. Dòng thứ $j + 2$ ($1 \le j \le n$) biểu thị thông tin của các ô ở hàng thứ $j$ tính từ trên xuống, gồm $m$ số nguyên $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$) cách nhau bởi dấu cách. Khi $c_{i,j} = -1$, điều đó có nghĩa là ô $(i, j)$ đã có người sinh sống. Ngược lại, nó biểu thị chi phí cần thiết để mua lại ô $(i, j)$ là $c_{i,j}$.

Lưu ý rằng đối với dữ liệu đầu vào dùng để chấm bài, việc xây dựng trung tâm thương mại là luôn thực hiện được.

Kết quả

Kết quả được ghi ra đầu ra chuẩn. Hãy in ra chi phí nhỏ nhất cần thiết để thu hồi đất xây dựng trung tâm thương mại.

Ví dụ

Dữ liệu vào 1

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

Kết quả 1

184

Vị trí xây dựng trung tâm thương mại trong ví dụ đầu vào/đầu ra này được minh họa như hình dưới đây. Các ô đánh dấu $\times$ có nghĩa là nơi đó đã có người sinh sống.

Lưu ý

Hãy chú ý đến kích thước của dữ liệu đầu vào. Đặc biệt, iostream trong C++ khá chậm, vì vậy bạn nên sử dụng fscanf hoặc các hàm tương tự khi cần thiết.