Rectangle and points

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Given a rectangle of size \(n \times m\) on the coordinate plane. The bottom-left corner of the rectangle is at the point \((0, 0)\), and the top-right corner is at \((n, m)\). Inside this rectangle, there are \(k\) points.

You need to move the rectangle (without rotating it and without changing its size) so that all \(k\) points end up on the boundaries or outside the rectangle. The movement can be in any direction on the plane. The distance by which the rectangle is moved is defined as the Euclidean distance between the initial position of the bottom-left corner \((0, 0)\) and the new position of this corner \((dx, dy)\).

Your task is to find the minimum distance the rectangle needs to be moved so that each of the \(k\) points ends up on the boundaries or outside the rectangle.

Input

The first line contains three integers \(n\), \(m\), \(k\) — the sizes of the rectangle and the number of points inside it.

The next \(k\) lines contain two integers \(x_i\), \(y_i\) each — the coordinates of the points located inside the rectangle.

Output

Output a single number — the minimum Euclidean distance by which the rectangle needs to be moved so that all \(k\) points end up outside its boundaries.

Constraints

\(2 \leq n, m \leq 10^9\),

\(1 \leq k \leq 2 \cdot 10^5\),

\(1 \leq x_i < n,\ 1 \leq y_i < m\).

Samples

Input (stdin) сopy	Output (stdout) сopy
10 10 3 1 4 2 2 3 1	2.2360679775

Notes

The distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is calculated using the formula \(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).

The red color shows the rectangle after movement, its bottom-left corner is at the point \((2, 1)\). Therefore, the distance by which it was moved is calculated as dist((0,0), (2,1)) = \(\sqrt{(2 - 0)^2 + (1 - 0)^2} = 2.2360679775\).