Hình chữ nhật

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một hình chữ nhật gồm \( N \) dòng và \( M \) cột. Các dòng được đánh số từ 1 đến \( N \) , từ trên xuống dưới. Các cột được đánh số từ 1 đến \( M \) , từ trái sang phải. Ô ở dòng thứ \( i \) và cột thứ \( j \) được gọi là ô (\( i, j \)) và có diện tích là 1 đơn vị. Có một số ô đã được điền sẵn kí tự \( 'X' \).

Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự \( 'X' \).

Input

  • Dòng đầu tiên gồm ba số nguyên dương \( N, M, K \)(\( N, M ≤ 10^4, K ≤ 10^3 \)) mô tả kích thước của hình chữ nhật và số lượng kí tự \( ′X′ \) có trong hình chữ nhật;
  • \(K\) dòng sau, mỗi dòng gồm hai số nguyên dương \( d \)\( c \) là chỉ số dòng và cột của ô điền kí tự \( ′X′ \) (\( d ≤ N; c ≤ M\)).

Output

  • Ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài..

Scoring

  • Có 50% số test tương ứng với 50% số điểm thoả mãn: \( N, M ≤ 50 \) ;
  • 30% số test khác tương ứng với 30% số điểm thoả mãn: \( N, M ≤ 500 \);
  • 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Example

Test 1
Input
4 5 4
2 3
2 5
3 1
4 4
Output
9

Bình luận