왕국 방어

시간 제한3초메모리 제한256 MB

요약
행과 열 전체를 방어하는 타워들이 배치된 격자에서, 방어되지 않는 가장 큰 직사각형의 넓이를 구합니다.
난이도

보통10점 중 5점

유형
정렬, 그리디, 배열
정답자
아직 제출이 없습니다

문제

테오도르는 "왕국 방어"라는 새로운 전략 게임을 만들고 있다. 각 단계에서 플레이어는 직사각형 격자로 표현되는 왕국을 방어한다. 플레이어는 격자의 일부 칸에 석궁 탑을 세운다. 하나의 탑은 자신과 같은 행과 같은 열에 있는 모든 칸을 방어한다. 어떤 두 탑도 같은 행이나 같은 열을 공유하지 않는다.

어떤 배치의 벌점은 방어되지 않는 가장 큰 직사각형에 포함된 칸의 수이다. 예를 들어 아래 그림에 나타난 배치의 벌점은 12이다.

주어진 배치의 벌점을 계산하는 프로그램을 작성하여라.

입력

첫째 줄에 세 정수 w, h, n이 주어진다. w는 격자의 너비, h는 격자의 높이, n은 석궁 탑의 개수이다 (1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h)).

이어지는 n개의 줄에는 각각 두 정수 xi와 yi가 주어지며, 이는 탑이 놓인 칸의 좌표이다 (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).

출력

어떤 탑에게도 방어되지 않는 가장 큰 직사각형에 포함된 칸의 수를 하나의 정수로 출력한다.

예제4

  1. 예제 1

    입력
    15 8 3
    3 8
    11 2
    8 6
    
    예상 출력
    12
    
  2. 예제 2

    입력
    5 5 0
    
    예상 출력
    25
    
  3. 예제 3

    입력
    10 10 1
    5 5
    
    예상 출력
    25
    
  4. 예제 4

    입력
    20 10 2
    5 3
    15 7
    
    예상 출력
    27