Gift Puzzle

Peyman's birthday party is being held. Keivan, his old friend, bought a puzzle as a birthday gift. The puzzle consists of a flat rectangular board with length $l$ and width $w$, and a thread. The board has $n$ horizontal rails of length $l$, each placed at a different distance from the top side. Each rail holds one obstacle that can slide freely along it. The figure shows an example of the board. The rails are drawn as dotted lines, and the obstacles are drawn as thick segments.

To solve the puzzle, one must connect the top-left corner of the board to the bottom-right corner with the thread. The thread must stay inside the board and cannot pass through any obstacle. The figure shows one way to solve the puzzle. Keivan believes Peyman can solve hard puzzles, so he wants to give Peyman the shortest thread that still connects the two corners. Help Keivan find the length of that thread.

The first line contains three integers $l$, $w$, and $n$. Here $l$ is the length of the board, $w$ is its width, and $n$ is the number of rails. The constraints are $2 \le l, w \le 10^9$ and $1 \le n \le \min(100\,000, w-1)$.

Each of the next $n$ lines contains two integers $y_i$ and $l_i$. Here $y_i$ is the distance between the $i$-th rail and the top side, and $l_i$ is the length of the obstacle on the $i$-th rail. The constraints are $1 \le y_i \le w-1$ and $1 \le l_i \le l-1$. All $y_i$ are distinct. Obstacles and the thread have zero width.

Print the minimum $t$ such that the obstacles can be placed so that the top-left corner connects to the bottom-right corner with a thread of length $t$ that avoids all obstacles. The answer is accepted if its relative error is at most $10^{-9}$.