AT_joig2022_d いちご 2 (Strawberry 2)

[problemUrl]: https://atcoder.jp/contests/joig2022-open/tasks/joig2022_d 果物好きのビ太郎は，いちごのつかみ取りに挑戦することにした．ビ太郎の目の前には $ 1 $ 脚の机がある．机は長方形の形をしており，縦 $ H $ 行，横 $ W $ 列のマス目状に区切られている．机には $ N $ 個のいちごが置かれており，$ i $ 番目 ($ 1\ \leqq\ i\ \leqq\ N $) のいちごは上から $ A_i $ 行目，左から $ B_i $ 列目のマスにある．複数のいちごが同じマスに置かれている可能性もある． ビ太郎は机から，縦 $ 3 $ 行，横 $ 3 $ 列の正方形の領域をなす $ 9 $ 個のマスを選び，それらのマスにあるいちごをすべて取る．この動作は $ 1 $ 回だけ行う． ビ太郎は，なるべく多くのいちごを取りたい． 机の大きさといちごの位置についての情報が与えられたとき，取れるいちごの個数の最大値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ H $ $ W $ $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

標準出力に，取れるいちごの個数の最大値を $ 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 $)． - 入力される値はすべて整数である． ### 小課題 1. ($ 14 $ 点) $ H\ \leqq\ 1\,000 $，$ W\ \leqq\ 1\,000 $，$ N\ \leqq\ 20 $． 2. ($ 16 $ 点) $ H\ \leqq\ 1\,000 $，$ W\ \leqq\ 1\,000 $． 3. ($ 29 $ 点) $ H\ \leqq\ 1\,000\,000 $，$ N\ \leqq\ 500 $． 4. ($ 15 $ 点) $ H\ =\ 3 $． 5. ($ 20 $ 点) $ H\ \leqq\ 1\,000\,000 $． 6. ($ 6 $ 点) 追加の制約はない． ### 採点に関する注意 すべての提出はジャッジシステム上で採点される． 提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる． 各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である． この課題の得点は，この課題に対するすべての提出の得点の最大値である． 現在の得点は「提出結果」タブの「自分の得点状況」から確認できる． ### Sample Explanation 1 いちごの配置は図のようになっている (赤い丸がいちごを表す)． !\[いちごの配置の図示\](https://img.atcoder.jp/joig2022/t4-1f63e2bb781109d23148a3974404ee6e894c98b639ae8375cd573fee0bcf50a1.png) 太枠で囲った領域をなすマスを選ぶことで，$ 5 $ 個のいちごが取れる． $ 5 $ 個よりも多くのいちごを取ることはできないので，$ 5 $ を出力する． この入力例は小課題 $ 1,\ 2,\ 3,\ 5,\ 6 $ の制約を満たす． ### Sample Explanation 2 複数のいちごが同じマスに置かれていることもある． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 3,\ 4,\ 5,\ 6 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 1,\ 2,\ 3,\ 5,\ 6 $ の制約を満たす．