17692번 - Cultivation 서브태스크다국어

In 21XX, the residents of the IOI planet plan to immigrate to a recently discovered planet.

The new planet has a field, which is a rectangular grid with R rows and C columns. The columns are parallel to the south-north direction, and the rows are parallel to the east-west direction. The cell in the i-th row from north and the j-th column from west is called the cell (i, j). The north-west corner of the field is the cell (1, 1), and the south-east corner is the cell (R,C). In each year, the residents of the IOI planet choose the direction of the wind blowing on the field. The direction is one of east, west, south, or north.

To engage in agriculture in the new planet, they will plant “JOI grasses” in all over the field in the new planet. In the spring of the first year of immigration, N cells in the field have JOI grasses.

The range of JOI grasses are expanded by the wind. Each summer, the seeds of JOI grasses are blown by the wind to the direction chosen by the residents of the IOI planet. The seeds move one cell to the direction of the wind, and they land on. If the seeds land on a cell of the field without JOI grasses, it will have JOI grasses in the spring of the next year. Once a cell has JOI grasses, it will keep JOI grasses in the future.

We want to calculate the minimum number of years until all the cells in the field have JOI grasses if we adjust the direction of the wind appropriately.

Write a program which calculates the minimum number of years until all the cells in the field have JOI grasses if we adjust the direction of the wind appropriately.

Read the following data from the standard input.

• The first line of input contains two space separated integers R, C. This means the field is a rectangular grid with R rows and C columns.
• The second line of input contains an integer N, the number of cells in the field which have JOI grasses in the spring of the first year of immigration.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains two space separated integers S_i, E_i. This means the cell (S_i, Ei) has JOI grasses in the spring of the first year of immigration.

Write one line to the standard output. The output contains the minimum number of years until all the cells in the field have JOI grasses if we adjust the direction of the wind appropriately.

• 1 ≤ N ≤ 300.
• 1 ≤ R ≤ 1 000 000 000.
• 1 ≤ C ≤ 1 000 000 000.
• 1 ≤ S_i ≤ R (1 ≤ i ≤ N).
• 1 ≤ E_i ≤ C (1 ≤ i ≤ N).
• In the spring of the first year of immigration, there is a cell in the field without JOI grasses.
• (S_i, E_i) ≠ (S_j, E_j) (1 ≤ i < j ≤ N).

• R ≤ 4.
• C ≤ 4.

• R ≤ 40.
• C ≤ 40.

• R ≤ 40.

• N ≤ 25.

• N ≤ 100.

There are no additional constraints.