Bohemian Rhaksody

시간 제한6.5초메모리 제한1024 MB

요약
N개의 전구가 각각 x≤X, x≥X, y≤Y, y≥Y 중 하나의 반평면을 비출 때, 모든 전구가 비추는 영역의 넓이가 최대가 되도록 각 전구의 방향을 정한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 기하, 구현
정답자
아직 제출이 없습니다

문제

MolaMola is a world-famous rock band composed of three members: Guitarist Sangsoo cki86201 Park famous for his amazing performance with Link-cut tree, drummer Sunggwan dotorya Park who plays 5 problems in 10 minutes without single WA, and the vocalist Bumsoo zlzmsrhak Park who is responsible for the impressive outlook of the band. The movie about their story, Bohemian Rhaksody, became a blockbuster in Korea, and they are preparing for their perfect comeback concert.

Bumsoo, famous for his unique sense of fashion, thinks that perfect concerts need not only the best music but also great visual effects. Needless to say, the illumination setting is a very important matter for him.

The stage given to them is a H×WH \times W size rectangle with four corners in (0,0),(0,W),(H,0),(H,W)(0, 0), (0, W), (H, 0), (H, W), and there are NN bulbs already installed in the stage. Note that the bulbs may lie on the boundary, but are not strictly outside. To prevent interference, each bulb has a distinct xx-coordinate, and each bulb also has a distinct yy-coordinate. Every bulb is designed to light either the east/west/south/north part of the stage. More formally, the bulb at the coordinate (X,Y)(X, Y) can be operated in one of the following modes:

  • Light the area of the stage where x≤Xx \le X. 
  • Light the area of the stage where x≥Xx \ge X.
  • Light the area of the stage where y≤Yy \le Y.
  • Light the area of the stage where y≥Yy \ge Y.

Bumsoo wants their band to play in the brightest area, so the stage will be exactly the area that is lit by all NN bulbs. Now, Bumsoo wants to find a way to operate the bulbs, in order to maximize the area of their stage. Help him!

입력

The first line contains three integers H,W,NH, W, N. (1≤N≤100000,1≤H,W≤1081 \le N \le 100000, 1 \le H, W \le 10^8)

In the next NN lines, two integers X,YX, Y are given, indicating that the bulb is installed in coordinate (X,Y)(X, Y). (0≤X≤H,0≤Y≤W0 \le X \le H, 0 \le Y \le W)

It is guaranteed that no pair of different bulbs share an xx-coordinate, and no pair of different bulbs share a yy-coordinate.

출력

Print the maximum possible area that can be lit by all NN bulbs.

예제3

  1. 예제 1

    입력
    4 4 5
    0 4
    1 3
    2 2
    3 1
    4 0
    
    예상 출력
    6
    
  2. 예제 2

    입력
    100000000 100000000 1
    0 0
    
    예상 출력
    10000000000000000
    
  3. 예제 3

    입력
    100000000 100000000 12
    100000000 59411855
    0 4914151
    57454627 45388814
    93661922 93279520
    81531691 0
    5221549 64790529
    75886863 85609174
    74950464 100000000
    18493301 57818271
    66752434 90450964
    44757377 54518291
    99631520 21997156
    
    예상 출력
    4522156529817280