Problem Description

There is a grid of squares with $ H $ rows and $ W $ columns, each square is painted either black or white. The square at the $ i $-th row from the top and the $ j $-th column from the left is called square $(i,\ j)$.

The squares $(a_i,\ b_i)\ (1\ \leq\ i\ \leq\ K)$ are painted white, and the remaining $H\ \times\ W\ -\ K$ squares are painted black.

For an integer $ k $ greater than or equal to $ 1 $, the grid contains an N of size $ k $ if there exist integers $i,\ j$ that satisfy the following conditions:

• All squares $(i\ +\ t,\ j)\ (0\ \leq\ t\ <\ k)$ are black
• All squares $(i\ +\ t,\ j\ +\ t)\ (0\ \leq\ t\ <\ k)$ are black
• All squares $(i\ +\ t,\ j\ +\ k\ -\ 1)\ (0\ \leq\ t\ <\ k)$ are black

Note that all squares involved in these conditions must be within the $ H $ rows and $ W $ columns of the grid.

Find the maximum size of the N contained in this grid. If no size of N is contained, output $ 0 $.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_K $ $ b_K $

Output Format

Output the maximum size of the N contained in the grid.

Sample Input and Output

Sample Input #1

3 4 2
1 3
3 3

Sample Output #1

3

Sample Input #2

2 2 4
2 1
1 1
1 2
2 2

Sample Output #2

0

Sample Input #3

2 2 2
1 1
2 2

Sample Output #3

1

Sample Input #4

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

Sample Output #4

4

Notes/Hints

Constraints

• $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)$
• All inputs are integers

Sample Explanation 1

The grid is in the following state (# represents black, and . represents white):

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

In this case, if $i\ =\ 1,\ j\ =\ 2$, the conditions are satisfied for $k\ =\ 3$, so the grid contains an N of size $ 3 $, which is the maximum.

Sample Explanation 2

The grid is in the following state:

..
..

No size of N is contained, so output $ 0 $.

Sample Explanation 3

The grid is in the following state:

.#
#.

If $i\ =\ 2,\ j\ =\ 1$ or $i\ =\ 1,\ j\ =\ 2$, the conditions are satisfied for $k\ =\ 1$.

Sample Explanation 4

The grid is in the following state:

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

见题面 Input 部分

见题面 Output 部分