가장 큰 (탄소 제로) 발자국

시간 제한2초메모리 제한512 MB

요약

n 곱하기 m 크기의 숲에 나무 좌표들이 주어질 때, 내부에 나무가 하나도 없는 가장 큰 축에 평행한 직사각형의 넓이를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 완전 탐색, 배열
정답자: 아직 제출이 없습니다

문제

복권에 당첨된 당신은 숲 속 깊은 곳에 여름 리조트를 짓기로 했습니다. 하지만 환경을 무척 아끼는 당신은 숲의 나무를 단 한 그루도 베지 않기로 합니다. 숲의 지도와 나무들의 위치가 주어질 때, 내부에 나무를 하나도 포함하지 않으면서 살 수 있는 가장 넓은 직사각형 부지의 넓이를 구하세요. 부지의 변은 반드시 $x$ 축과 $y$ 축에 평행해야 합니다.

부지의 변(경계) 위에 놓인 나무는 괜찮으며, 부지 내부에 완전히 들어오는 나무만 허용되지 않습니다.

입력

첫째 줄에 세 정수 $n$ , $m$ , $t$ ( $0 < n, m < 10000$ , $0 < t < 10000$ )가 주어집니다. 각각 숲 지도의 가로 크기, 세로 크기, 그리고 나무의 개수를 의미합니다.

다음 $t$ 개의 줄에는 각 나무의 위치를 나타내는 두 정수 $x$ , $y$ ( $0 \le x \le n$ , $0 \le y \le m$ )가 주어집니다. 점 $(0, 0)$ 은 지도의 왼쪽 아래 꼭짓점이고, 점 $(n, m)$ 은 오른쪽 위 꼭짓점입니다.

출력

주어진 나무를 내부에 하나도 포함하지 않는, 축에 평행한 가장 넓은 직사각형의 넓이를 정수 하나로 출력하세요.

예제3

예제 1
입력
```
5 5 2
1 1
3 3
```
예상 출력
```
12
```
예제 2
입력
```
10 10 2
1 5
9 5
```
예상 출력
```
80
```
예제 3
입력
```
10 10 1
5 5
```
예상 출력
```
50
```