유리 자르기
면접 대비시간 제한1초메모리 제한1024 MB
가로 M, 세로 N인 유리판에 결함 K개가 주어질 때, 결함이 내부에 없는 가장 큰 직사각형의 넓이를 구합니다.
문제
아르투라스는 새 온실의 틀을 짜 놓았고, 이제 유리를 끼울 참이다. 그는 길이 , 너비 인 직사각형 유리판을 샀는데, 집에 가져와 보니 결함이 개 있었다. 결함은 모두 작아서 점으로 보면 되고, 그 자리는 유리에 약간 금이 가 있는 곳이다.
아르투라스는 품질이 나쁜 유리를 쓰고 싶지 않아서, 유리판에서 결함이 없는 직사각형 중 넓이가 가장 큰 것을 잘라내려 한다.
아르투라스에게는 유리판을 올려놓고 변과 평행한 가로와 세로 방향으로 선을 그어 자르는 장치가 있다. 장치가 아주 정밀해서, 자르는 선이 결함 위를 지나가도 유리는 깨지지 않는다.
아르투라스가 유리판에서 잘라낼 수 있는, 결함이 없는 직사각형의 최대 넓이를 구하시오.
결함은 잘라낸 직사각형의 가장자리에 있어도 되지만, 직사각형 내부에는 결함이 하나도 있으면 안 된다.
입력
첫 줄에 정수 , , 가 주어진다. 이어서 개의 줄에 결함의 좌표 와 가 각각 두 정수로 주어진다.
처음 유리판의 왼쪽 아래 모서리 좌표는 이고, 오른쪽 위 모서리 좌표는 이다.
항상 , 이다. 또한 모든 결함의 좌표는 서로 다르다.
출력
정수 하나를 출력한다. 아르투라스가 유리판에서 잘라낼 수 있는 결함 없는 직사각형의 최대 넓이이다.
제한
,