만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

유리 자르기

면접 대비

시간 제한1초메모리 제한1024 MB

요약
가로 M, 세로 N인 유리판에 결함 K개가 주어질 때, 결함이 내부에 없는 가장 큰 직사각형의 넓이를 구합니다.
난이도

보통10점 중 5점

유형
정렬, 완전 탐색, 배열
정답자
아직 제출이 없습니다

문제

아르투라스는 새 온실의 틀을 짜 놓았고, 이제 유리를 끼울 참이다. 그는 길이 MM, 너비 NN인 직사각형 유리판을 샀는데, 집에 가져와 보니 결함이 KK개 있었다. 결함은 모두 작아서 점으로 보면 되고, 그 자리는 유리에 약간 금이 가 있는 곳이다.

아르투라스는 품질이 나쁜 유리를 쓰고 싶지 않아서, 유리판에서 결함이 없는 직사각형 중 넓이가 가장 큰 것을 잘라내려 한다.

아르투라스에게는 유리판을 올려놓고 변과 평행한 가로와 세로 방향으로 선을 그어 자르는 장치가 있다. 장치가 아주 정밀해서, 자르는 선이 결함 위를 지나가도 유리는 깨지지 않는다.

아르투라스가 유리판에서 잘라낼 수 있는, 결함이 없는 직사각형의 최대 넓이를 구하시오.

결함은 잘라낸 직사각형의 가장자리에 있어도 되지만, 직사각형 내부에는 결함이 하나도 있으면 안 된다.

입력

첫 줄에 정수 MM, NN, KK가 주어진다. 이어서 KK개의 줄에 결함의 좌표 XX와 YY가 각각 두 정수로 주어진다.

처음 유리판의 왼쪽 아래 모서리 좌표는 (0,0)(0, 0)이고, 오른쪽 위 모서리 좌표는 (M,N)(M, N)이다.

항상 1≤X≤M−11 \le X \le M-1, 1≤Y≤N−11 \le Y \le N-1이다. 또한 모든 결함의 좌표는 서로 다르다.

출력

정수 하나를 출력한다. 아르투라스가 유리판에서 잘라낼 수 있는 결함 없는 직사각형의 최대 넓이이다.

제한

2≤M,N≤300002 \le M, N \le 30000, 1≤K≤5001 \le K \le 500

예제1

  1. 예제 1

    입력
    8 4 2
    1 3
    7 2
    
    예상 출력
    24