CSS IS AWESOME
시간 제한2초메모리 제한1024 MB
주어진 W×H 판에서 N개의 직사각형과 겹치지 않는 가장 넓은 축 정렬 직사각형을 구한다.
문제
프리랜서 웹 개발자로 일하고 있는 진호는 웹 사이트에 광고 게재를 도와달라는 의뢰를 받았다.
웹사이트와 기존에 게재된 모든 광고, 진호가 게재할 광고는 모두 축과 축에 각 변이 평행한 직사각형이며, 웹사이트 레이아웃은 왼쪽 위가 원점인 이고, 오른쪽으로 갈수록 값이 증가하고 아래쪽으로 갈수록 값이 증가한다.
광고가 가려서 보이지 않게 하는 것은 예의가 아니기 때문에, 진호는 이미 게재된 광고는 무조건 가리지 않도록 하려고 한다. 한 점에서 만나거나 변끼리 접하는 것은 가리는 것으로 치지 않는다.
하지만 광고 효과가 크기 위해서는 광고의 넓이를 최대한 키울 필요가 있다. 진호가 게재할 수 있는 가장 넓은 직사각형 모양 광고의 넓이를 구해보자.
입력
첫째 줄에 웹사이트의 가로와 세로 크기를 나타내는 두 정수 , 와 이미 게재된 광고의 수 이 공백으로 구분되어 주어진다.
둘째 줄부터 개의 줄에 걸쳐 이미 게재된 광고의 왼쪽 위, 오른쪽 아래 좌표를 나타내는 개의 정수 , , , 가 공백으로 구분되어 주어진다.
이미 게재된 광고는 서로 겹칠 수도 있다.
출력
진호가 게재할 수 있는 가장 넓은 광고의 넓이를 출력한다.