G. Gas Stations
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

A group of friends is planning a road trip from Patras to Thessaloniki. They have chosen their main route, but visiting a gas station may require a detour.

Their car travels along a main route from position $$$0$$$ to position $$$d$$$. On a full tank, it can travel $$$l$$$ kilometers. Initially, its tank is full.

There are $$$n$$$ refueling stations. Station $$$i$$$ is connected to the main route at position $$$p_i$$$. To visit it, the car leaves the route, travels $$$a_i/2$$$ kilometers to the station, fills its tank completely, and travels $$$a_i/2$$$ kilometers back to the same position on the main route. Thus, visiting this station adds $$$a_i$$$ kilometers to the journey. Fuel is consumed on both parts of the detour, at the same constant rate as on the main route.

The car moves only forward along the main route. The positions of the stations it visits must strictly increase. The car may arrive at a station or at the destination with an empty tank. The distance traveled between consecutive refuelings, as well as before the first and after the last refueling, must not exceed $$$l$$$.

Find the minimum total distance the car must travel to reach position $$$d$$$, including all detours. If reaching the destination is impossible, report this.

Input

The first line contains an integer $$$d$$$ ($$$1 \le d \le 10^9$$$), the length of the main route in kilometers.

The second line contains an integer $$$l$$$ ($$$1 \le l \le 10^6$$$), the distance in kilometers that the car can travel on a full tank.

The third line contains an integer $$$n$$$ ($$$0 \le n \le 10^5$$$), the number of stations.

Each of the next $$$n$$$ lines contains two integers $$$p_i$$$ and $$$a_i$$$ ($$$1 \le p_i \le d-1$$$, $$$0 \le a_i \le 10^6$$$), the position of station $$$i$$$ on the main route and the total length of its detour. The stations are given in strictly increasing order of position: $$$p_1 \lt p_2 \lt \dots \lt p_n$$$. If $$$d=1$$$, then $$$n=0$$$.

Output

Print one integer: the minimum total distance traveled, or $$$-1$$$ if the destination cannot be reached.

Examples
Input
300
150
4
100 2
130 5
230 30
270 5
Output
310
Input
20
10
1
12 0
Output
-1
Input
10
10
0
Output
10