日本情報オリンピック 第2回 女性部門

2022年1月24日
情報オリンピック日本委員会

問題文

果物好きのビ太郎は，いちごのつかみ取りに挑戦することにした．ビ太郎の目の前には 1 脚の机がある．机は長方形の形をしており，縦 H 行，横 W 列のマス目状に区切られている．机には N 個のいちごが置かれており，i 番目 (1 ≦ i ≦ N) のいちごは上から A_i 行目，左から B_i 列目のマスにある．複数のいちごが同じマスに置かれている可能性もある．

ビ太郎は机から，縦 3 行，横 3 列の正方形の領域をなす 9 個のマスを選び，それらのマスにあるいちごをすべて取る．この動作は 1 回だけ行う．

ビ太郎は，なるべく多くのいちごを取りたい．

机の大きさといちごの位置についての情報が与えられたとき，取れるいちごの個数の最大値を求めるプログラムを作成せよ．

制約

• 3 ≦ H ≦ 1 000 000 000．
• 3 ≦ W ≦ 1 000 000 000．
• 1 ≦ N ≦ 60 000．
• 1 ≦ A_i ≦ H (1 ≦ i ≦ N)．
• 1 ≦ B_i ≦ W (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (14 点) H ≦ 1 000，W ≦ 1 000，N ≦ 20．
2. (16 点) H ≦ 1 000，W ≦ 1 000．
3. (29 点) H ≦ 1 000 000，N ≦ 500．
4. (15 点) H = 3．
5. (20 点) H ≦ 1 000 000．
6. (6 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．
H W
N
A₁ B₁
A₂ B₂
:
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 の制約を満たす．