소 연못
면접 대비시간 제한1초메모리 제한1024 MB
W×H 크기의 숲에서 나무가 없는 격자점만 덮는 가장 큰 L자 모양 수영장의 격자점 개수를 구합니다.
문제
소들은 내년 여름에 쓸 수영장이 꼭 있어야 한다고 결정했다. 모양도 정했는데, 'L'자 모양의 수영장을 원한다. 수영장은 목초지 근처의 숲에 만들 예정이고, 나무는 한 그루도 베지 않으려 한다. 숲의 크기는 가로 W, 세로 H이며 나무 N개의 위치가 주어진다. 숲 안에 만들 수 있는 수영장 중 넓이가 가장 큰 것을 구하라.
아래는 가장 큰 수영장을 배치한 격자와 숲의 예시이다.
. . * . . . . . . * . . . .
* . . . . . . * P P . . . .
. . . * * * . . P P * * * .
. . . . . . . . P P . . . .
* . . * . * . -> * P P * . * .
. . . . . . . . P P P P P .
. . . . . . . . P P P P P .
* . . . . . * * P P P P P *
. . * . * . . . . * . * . .
가장 큰 수영장은 격자점 23개를 덮는다.
수영장은 'L'자 모양이며, 왼쪽 아래 모서리를 공유하는 두 직사각형을 합친 형태이다. 'L'의 아래 막대는 위쪽 부분보다 넓어야 한다. 위쪽 부분은 아래 막대보다 높아야 한다. 'L'자는 회전하거나 뒤집을 수 없다. 단순한 직사각형은 'L'자가 아니다.
입력
첫 줄에 정수 세 개 W (5 ≤ W ≤ 150), H (5 ≤ H ≤ 150), N (1 ≤ N ≤ 20000)이 주어진다.
이어지는 N개의 줄에는 각각 나무의 행과 열을 나타내는 정수 두 개가 주어진다. 나무 지도의 왼쪽 위 모서리가 1행 1열이다. 위 예시에서 맨 윗줄의 1행 3열에 나무가 있다.
출력
가장 큰 수영장이 덮는 격자점의 개수를 한 줄에 출력한다.