#504. GOLFYARD – Sân Golf

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Sau nhiều lần tham gia giải Golf quốc tế PGA Tour và giành được nhiều giải thưởng, Tiger Woods quyết định đầu tư số tiền này để xây dựng một sân golf mang tên mình.

Sân golf mà Tiger Woods định xây nằm trong khuôn viên một khu đất hình chữ nhật kích thước M × N đã được chia thành lưới M hàng và N cộ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. Ô đất tại hàng i , cột j có độ cao là h_{ij} . Tiger Woods sẽ chọn một hình chữ nhật con gồm các ô đất thuộc lưới để xây sân golf sao cho với hình chữ nhật con này thì các số trên một hàng bất kỳ tính từ trái sang phải, các số trên một cột bất kỳ tính từ trên xuống dưới đều có độ cao không giảm. Sau đó, Tiger Woods sẽ đặt lỗ golf tại góc trái trên và vị trí bắt đầu đánh tại góc phải dưới của hình chữ nhật để khi đánh, quả bóng luôn lăn xuống lỗ (do quá mệt mỏi với việc thi đấu các giải đấu lớn rồi nên Tiger Woods chỉ muốn xây một sân golf mang tính giải trí cao).

Bạn hãy giúp Tiger Woods chọn được sân golf có diện tích lớn nhất thỏa mãn yêu cầu trên.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương M N (là số hàng và số cột của khu đất).
  • M dòng tiếp theo, dòng thứ i chứa N số nguyên dương h_{i1}, h_{i2}, …, h_{iN} .

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

  • Một số nguyên dương duy nhất là diện tích lớn nhất của sân golf xây được.

Ví dụ:

Dữ liệu vào:
3 4
9 2 4 8
3 5 7 8
6 8 1 3
Dữ liệu ra:
6
Giải thích:
  • Khu đất chọn để xây sân golf có tọa độ trái trên là (1, 2) , phải dưới là (2, 4) tổng diện tích là 6 ô đơn vị.

Giới hạn:

  • 1 ≤ M, N ≤ 10^3; 1 ≤ h_i ≤ 10^9 .