Food Processor

문제

You have a food processor with a variety of blades that can be attached to it, as well as some food you would like to process into smaller pieces.

The food processor can have one blade attached at any time. Each blade processes food by reducing its average piece size at a particular exponential rate, but it also has a maximum average piece size requirement; if the average piece size of the food is too big for the blade, the food processor will get stuck. Given a starting average food piece size, a target average piece size, and a set of blades for your food processor, determine the minimum amount of processing time needed to process your food into the target average piece size.

Note that we only care about the time spent actively processing food; we do not track time spent switching out blades or loading/unloading the food processor.

입력

The first line of input contains three integers $ss$, $tt$, and $nn$ (), where $ss$ is the starting average piece size, $tt$ is the target average piece size, and $nn$ is the number of blades.

Each of the next $nn$ lines contains two integers $mm$ and $hh$ ($1\le m,h\le {10}^{6}1\; \backslash le\; m,\; h\; \backslash le\; 10^6$). These are the blades, where $mm$ is the maximum average piece size of the blade and $hh$ is the number of seconds the blade needs to halve the average piece size.

출력

Output a single number, which is the minimum amount of time in seconds needed to process the food to the target average piece size. If it is not possible to reach the target, output $-1-1$. Your answer should have a relative error of at most ${10}^{-5}10^\{-5\}$.