시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 113 49 41 44.565%

문제

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

제한

  • 1 ≤ H, W, N ≤ 100
  • 1 ≤ Ri, Ci ≤ 100

예제 입력 1

2 2
2
1 2
2 1

예제 출력 1

4

예제 입력 2

10 9
4
2 3
1 1
5 10
9 11

예제 출력 2

56

예제 입력 3

10 10
3
6 6
7 7
20 5

예제 출력 3

0

출처