いちご 2 (Strawberry 2)

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

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