Bản đồ Byteland được vẽ trên một lưới \(n\times m\), trong đó \(n\) là chiều dọc và \(m\) là chiều ngang. Các đường ngang được gọi là vĩ tuyến và đánh số từ \(0\) đến \(n\); các đường dọc được gọi là kinh tuyến và đánh số từ \(0\) đến \(m\).

Mỗi ô đơn vị cần một khoảng thời gian nhất định để tính dự báo thời tiết. Hệ thống cũ xử lý lần lượt tất cả các ô, nên tổng thời gian bằng tổng thời gian của từng ô.

Hệ thống mới dùng nhiều bộ xử lý. Ta chọn \(r\) vĩ tuyến và \(s\) kinh tuyến để chia bản đồ thành \((r+1)(s+1)\) hình chữ nhật. Mỗi bộ xử lý phụ trách một hình chữ nhật, với thời gian bằng tổng thời gian của các ô nằm trong đó. Thời gian hoàn tất toàn bộ dự báo là giá trị lớn nhất trong thời gian của các bộ xử lý.

Hãy chọn các đường chia sao cho thời gian hoàn tất là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên \(n,m,r,s\) (\(1\le r<n\le18\), \(1\le s<m\le18\)).

\(n\) dòng tiếp theo chứa thời gian của các ô. Số thứ \(j\) trên dòng thứ \(i\) là \(c_{i,j}\) — thời gian của ô nằm giữa vĩ tuyến \(i-1\) và \(i\), đồng thời giữa kinh tuyến \(j-1\) và \(j\) (\(0\le c_{i,j}\le2\,000\,000\)).

Dữ liệu ra

In một số nguyên — thời gian hoàn tất nhỏ nhất có thể.

Phân nhóm

1. 40 điểm: \(n,m\le10\).
2. 60 điểm: không có ràng buộc bổ sung.

Ví dụ

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

31