Một khu đất có dạng hình chữ nhật kích thước m x n (đơn vị diện tích). Khu đất được chia thành m x n ô vuông đơn vị có cạnh là 1 đơn vị dài. Mỗi ô vuông đã được niêm yết giá và công ty nhà đất chỉ bán theo từng ô vuông đơn vị.

Để xây k biệt thự, phú ông cần phải chọn k mảnh đất hình vuông không giao nhau với tổng số tiền không vượt quá t đồng.

Yêu cầu: Cho giá đất của từng ô đất t và k, hãy tìm k mảnh đất thích hợp để xây biệt thự với diện tích lớn nhất.

Dữ liệu:

- Dòng 1: Chứa ba số nguyên m, n và k là kích thước khu đất;
- Dòng 2: Chứa số nguyên t là kinh phí để mua đất;
- m tiếp theo, mỗi dòng chứa n số nguyên dương cách nhau thể hiện giá của các ô đất, mỗi số không vượt quá 10⁹.

Kết quả:

Ghi ra một số duy nhất là tổng diện tích lớn nhất có thể của k mảnh đất hình vuông dùng để xây biệt thự. Nếu không có thì ghi ra 0.