만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

딸기 2

면접 대비

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

요약
거대한 격자 위에 3×3 정사각형을 놓아 포함되는 점의 수가 최대가 되도록 한다.
난이도

보통10점 중 5점

유형
슬라이딩 윈도우, 정렬, 배열, 구현
정답자
아직 제출이 없습니다

문제

과일을 좋아하는 비타로는 딸기 움켜쥐기에 도전하기로 했다. 비타로 앞에는 책상이 1개 있다. 책상은 직사각형이고 세로 H행, 가로 W열의 격자로 나뉘어 있다. 책상 위에는 딸기 N개가 놓여 있으며, i번째(1 ≦ i ≦ N) 딸기는 위에서 Ai행, 왼쪽에서 Bi열 칸에 있다. 여러 딸기가 같은 칸에 놓여 있을 수도 있다.

비타로는 책상에서 세로 3행, 가로 3열의 정사각형 영역을 이루는 9개 칸을 골라 그 칸에 있는 딸기를 모두 딴다. 이 동작은 1번만 한다.

비타로는 되도록 많은 딸기를 따고 싶다.

책상의 크기와 딸기 위치 정보가 주어졌을 때, 딸 수 있는 딸기 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

H W
N
A1 B1
A2 B2
:
AN BN

출력

표준 출력에 딸 수 있는 딸기 개수의 최댓값을 1행으로 출력하시오.

제한

  • 3 ≦ H ≦ 1 000 000 000.
  • 3 ≦ W ≦ 1 000 000 000.
  • 1 ≦ N ≦ 60 000.
  • 1 ≦ Ai ≦ H (1 ≦ i ≦ N).
  • 1 ≦ Bi ≦ W (1 ≦ i ≦ N).
  • 입력되는 값은 모두 정수이다.

예제4

  1. 예제 1

    입력
    4 5
7
1 1
1 5
2 2
2 4
3 3
4 2
4 4
    예상 출력
    5

  2. 예제 2

    입력
    3 5
6
1 1
1 2
2 1
2 4
2 4
3 4
    예상 출력
    4

  3. 예제 3

    입력
    3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815
    예상 출력
    9

  4. 예제 4

    입력
    11 11
20
7 7
6 11
5 7
8 8
9 9
5 5
8 4
4 4
4 8
2 6
1 6
6 2
3 3
9 3
7 5
6 1
10 6
6 10
11 6
3 9
    예상 출력
    4