問題文

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 < k) がすべて黒
• マス (i + t, j + t) (0 \leq t < k) がすべて黒
• マス (i + t, j + k - 1) (0 \leq t < k) がすべて黒

ただし、この条件に関わる全てのマスが H 行 W 列のマス目に含まれなければなりません。

このマス目に含まれる N のサイズの最大値を求めてください。ただし、どのサイズの N も含まない場合は、0 を出力してください。

制約

• 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)
• 入力は全て整数である

入力例 1

3 4 2
1 3
3 3

出力例 1

3

マス目は以下の状態になっています。(# が黒、. が白で塗られていることを表しています)

##.#  
####  
##.#

このとき、i = 1, j = 2 とすれば k = 3 に対して条件を満たすのでこのマス目はサイズ 3 の N を含み、これが最大です。

入力例 2

2 2 4
2 1
1 1
1 2
2 2

出力例 2

0

マス目は以下の状態になっています。

..  
..

どのサイズの N も含まれないので、0 を出力してください。

入力例 3

2 2 2
1 1
2 2

出力例 3

1

マス目は以下の状態になっています。

.#  
#.

i = 2, j = 1 または i = 1, j = 2 とすれば k = 1 に対して条件を満たします。

入力例 4

4 4 5
2 3
1 3
4 2
4 3
3 2

出力例 4

4

マス目は以下の状態になっています。

##.#  
##.#  
#.##  
#..#