시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB105403536.842%

문제

果物好きのビ太郎は,いちごのつかみ取りに挑戦することにした.ビ太郎の目の前には 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).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
114

H ≦ 1 000W ≦ 1 000N ≦ 20

216

H ≦ 1 000W ≦ 1 000

329

H ≦ 1 000 000N ≦ 500

415

H = 3

520

H ≦ 1 000 000

66

追加の制約はない.

예제 입력 1

4 5
7
1 1
1 5
2 2
2 4
3 3
4 2
4 4

예제 출력 1

5

いちごの配置は図のようになっている (赤い丸がいちごを表す).

太枠で囲った領域をなすマスを選ぶことで,5 個のいちごが取れる.

5 個よりも多くのいちごを取ることはできないので,5 を出力する.

この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす.

예제 입력 2

3 5
6
1 1
1 2
2 1
2 4
2 4
3 4

예제 출력 2

4

複数のいちごが同じマスに置かれていることもある.

この入力例はすべての小課題の制約を満たす.

예제 입력 3

3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815

예제 출력 3

9

この入力例は小課題 3, 4, 5, 6 の制約を満たす.

예제 입력 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

4

この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.