Thu hoạch ngô

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Ams2
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

An được giao nhiệm vụ thu hoạch ~K~ kg ngô trên cánh đồng của gia đình được chia thành ~m * n~ ô vuông và lượng ngô tại mỗi ô đã biết. Các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Để tiện cho việc quản lí, An phải chọn ra một khu đất có hình chữ nhật trên cánh đồng để thu hoạch. Vì không muốn mất nhiều thời gian, An phải tìm ra khu đất có diện tích nhỏ nhất sao cho vẫn đủ ngô để thu hoạch. Hãy giúp An thực hiện công việc này!

INPUT

Dòng thứ nhất ghi ba số ~m, n, k~ (~1 \le m, n < 500~, ~1 \le k \le 10^9~). Dòng thứ ~i~ trong ~m~ dòng tiếp theo ghi ~n~ số nguyên không âm, trong đó số thứ ~j~ cho biết lượng ngô tại ô (~i, j~). Biết lượng ngô tại mỗi ô không vượt quá ~10^4~ kg.

OUTPUT

Nếu không tồn tại vùng nào cho đủ lượng ngô cần thu hoạch, in ra ~-1~. Ngược lại in ra:

  • Dòng thứ nhất ghi diện tích nhỏ nhất có thể của vùng thu hoạch ngô.
  • Dòng tiếp theo ghi bốn số là chỉ số của góc trái trên và góc phải dưới của vùng thu hoạch ngô. Nếu có nhiều vùng cùng thỏa mãn thì in ra tọa độ của một vùng bất kỳ.

SAMPLE INPUT

3 3 19
5 4 0
4 7 0 
0 0 2

SAMPLE OUTPUT

4
1 1 2 2