AT_nikkei2019_2_final_c Largest N

[problemUrl]: https://atcoder.jp/contests/nikkei2019-2-final/tasks/nikkei2019_2_final_c $ H $ 行 $ W $ 列 のマス目があり、それぞれのマスは黒または白で塗られています。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,\ j) $ と呼びます。 マス $ (a_i,\ b_i)\ (1\ \leq\ i\ \leq\ K) $ は白で塗られており、それ以外の $ H\ \times\ W\ -\ K $ マスは黒で塗られています。 $ 1 $ 以上の整数 $ k $ に対してマス目がサイズ $ k $ の `N` を含むとは、次の条件をみたす整数 $ i,\ j $ が存在することを言います。 - マス $ (i\ +\ t,\ j)\ (0\ \leq\ t\

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_K $ $ b_K $

マス目に含まれる `N` のサイズの最大値を出力せよ。

### 制約 - $ 1\ \leq\ H,\ W\ \leq\ 3000 $ - $ 0\ \leq\ K\ \leq\ \mathrm{min}(H\ \times\ W,\ 2\ \times\ 10^5) $ - $ 1\ \leq\ a_i\ \leq\ H $ - $ 1\ \leq\ b_i\ \leq\ W $ - $ (a_i,\ b_i)\ \neq\ (a_j,\ b_j)\ (i\ \neq\ j) $ - 入力は全て整数である ### Sample Explanation 1 マス目は以下の状態になっています。(`#` が黒、`.` が白で塗られていることを表しています) ``` ##.# #### ##.# ``` このとき、$ i\ =\ 1,\ j\ =\ 2 $ とすれば $ k\ =\ 3 $ に対して条件を満たすのでこのマス目はサイズ $ 3 $ の `N` を含み、これが最大です。 ### Sample Explanation 2 マス目は以下の状態になっています。 ``` .. .. ``` どのサイズの `N` も含まれないので、$ 0 $ を出力してください。 ### Sample Explanation 3 マス目は以下の状態になっています。 ``` .# #. ``` $ i\ =\ 2,\ j\ =\ 1 $ または $ i\ =\ 1,\ j\ =\ 2 $ とすれば $ k\ =\ 1 $ に対して条件を満たします。 ### Sample Explanation 4 マス目は以下の状態になっています。 ``` ##.# ##.# #.## #..# ```