Contest Supervision III

You are tasked with supervising yet another contest. The contest room is laid out like a grid, with desks in $R$ rows (numbered from $0$ to $R-1$) and $C$ columns (numbered from $0$ to $C-1$). These rows and columns are all spaced 2 meters apart. $N$ of the chairs in rows $1$ to $r-1$ are occupied by contestants. You will sit at a desk in row $0$, facing the contestants.

However, you woke up late and lost your glasses running to the contest venue. Because you now can't see very well, you want to minimise the amount you'll be straining your eyes. The eye strain at any desk you sit at is the distance to the furthest contestant from your desk. Which desk should you sit at to minimise your eye strain?

Input Format

• The first line contains the integers $R$ and $C$ - the number of rows and columns of desks.
• The second line contains the integer $N$ - the number of contestants
• Each of the next $N$ lines is of the form $r_i$ $c_i$, indicating that the $i-th$ contestant is sitting at row $r_i$ and column $c_i$.

Output Format

Output a single number - the column of the desk you should sit in to minimise your eye strain. You only need to output the column because you must sit in row 0.

If there are multiple columns that will result in the same minimum eye strain, choose the the lower numbered column.

Constraints

For all subtasks:

• $1 \le N \le 100,000$
• $2 \le R \le 1,000,000,000$
• $2 \le C \le 1,000,000,000$
• $1 \le r_i \le R-1$ for all $i$
• $0 \le c_i \le C-1$ for all $i$
• No two contestants sit at the same desk

Subtasks

• Subtask 1 (+15%): $N = 1$ and $C, R \le 1,000$.
• Subtask 2 (+25%): $N, R, C \le 1,000$.
• Subtask 3 (+25%): $N, R \le 1,000$.
• Subtask 4 (+35%): No further constraints apply.

Sample Explanations

Sample 1

In this case, contestant 0 is at row 1 and column 1, contestant 1 is at row 1 and column 9, and contestant 2 is at row 8 and column 5. If you sit at column 5 in row 0, then the furthest contestant from you is contestant 2. The eye strain if you sit there is the distance to contestant 2, which is 8 meters away. At any other column in row 0, the distance to the furthest contestant will be larger than 8 meters, so you should sit in column 5.

Sample 2

In this case, if you sit at column 4 then the furthest contestant is 5 meters away at row 3 and column 8. The furthest contestant if you sit at column 5 is at row 3 and column 1, and they are also 5 meters away from you. The eye strain if you sit at any other column is more than 5 meters. Because both column 4 and 5 give you the lowest eye strain, you should sit in the lower numbered one, namely column 4.

Note: Python submissions should use Python 3.6 (PyPy 7.3), as submissions using Python 3.8 may not be fast enough to pass some subtasks.