Educational Codeforces Round 27 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Fire in the City

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe capital of Berland looks like a rectangle of size *n* × *m* of the square blocks of same size.

Fire!

It is known that *k* + 1 blocks got caught on fire (*k* + 1 ≤ *n*·*m*). Those blocks are centers of ignition. Moreover positions of *k* of these centers are known and one of these stays unknown. All *k* + 1 positions are distinct.

The fire goes the following way: during the zero minute of fire only these *k* + 1 centers of ignition are burning. Every next minute the fire goes to all neighbouring blocks to the one which is burning. You can consider blocks to burn for so long that this time exceeds the time taken in the problem. The neighbouring blocks are those that touch the current block by a side or by a corner.

Berland Fire Deparment wants to estimate the minimal time it takes the fire to lighten up the whole city. Remember that the positions of *k* blocks (centers of ignition) are known and (*k* + 1)-th can be positioned in any other block.

Help Berland Fire Department to estimate the minimal time it takes the fire to lighten up the whole city.

Input

The first line contains three integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 10^{9}, 1 ≤ *k* ≤ 500).

Each of the next *k* lines contain two integers *x*_{i} and *y*_{i} (1 ≤ *x*_{i} ≤ *n*, 1 ≤ *y*_{i} ≤ *m*) — coordinates of the *i*-th center of ignition. It is guaranteed that the locations of all centers of ignition are distinct.

Output

Print the minimal time it takes the fire to lighten up the whole city (in minutes).

Examples

Input

7 7 3

1 2

2 1

5 5

Output

3

Input

10 5 1

3 3

Output

2

Note

In the first example the last block can have coordinates (4, 4).

In the second example the last block can have coordinates (8, 3).

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/22/2024 13:11:33 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|