Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
果物好きのビ太郎は,いちごのつかみ取りに挑戦することにした.ビ太郎の目の前には 1 脚の机がある.机は長方形の形をしており,縦 H 行,横 W 列のマス目状に区切られている.机には N 個のいちごが置かれており,i 番目 (1 \leqq i \leqq N) のいちごは上から A_i 行目,左から B_i 列目のマスにある.複数のいちごが同じマスに置かれている可能性もある.
ビ太郎は机から,縦 3 行,横 3 列の正方形の領域をなす 9 個のマスを選び,それらのマスにあるいちごをすべて取る.この動作は 1 回だけ行う.
ビ太郎は,なるべく多くのいちごを取りたい.
机の大きさといちごの位置についての情報が与えられたとき,取れるいちごの個数の最大値を求めるプログラムを作成せよ.
制約
- 3 \leqq H \leqq 1\,000\,000\,000.
- 3 \leqq W \leqq 1\,000\,000\,000.
- 1 \leqq N \leqq 60\,000.
- 1 \leqq A_i \leqq H (1 \leqq i \leqq N).
- 1 \leqq B_i \leqq W (1 \leqq i \leqq N).
- 入力される値はすべて整数である.
小課題
- (14 点) H \leqq 1\,000,W \leqq 1\,000,N \leqq 20.
- (16 点) H \leqq 1\,000,W \leqq 1\,000.
- (29 点) H \leqq 1\,000\,000,N \leqq 500.
- (15 点) H = 3.
- (20 点) H \leqq 1\,000\,000.
- (6 点) 追加の制約はない.
採点に関する注意
すべての提出はジャッジシステム上で採点される.
提出されたソースコードは,小課題に対応するすべての採点用入力データについて正しい結果を返したとき,その小課題について正解と認められる.
各提出の得点は,提出されたソースコードについて正解と認められた小課題の得点の合計である.
この課題の得点は,この課題に対するすべての提出の得点の最大値である.
現在の得点は「提出結果」タブの「自分の得点状況」から確認できる.
入力
入力は以下の形式で標準入力から与えられる.
H W N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
標準出力に,取れるいちごの個数の最大値を 1 行で出力せよ.
入力例 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 の制約を満たす.