Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Package Delivery

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJohnny drives a truck and must deliver a package from his hometown to the district center. His hometown is located at point 0 on a number line, and the district center is located at the point *d*.

Johnny's truck has a gas tank that holds exactly *n* liters, and his tank is initially full. As he drives, the truck consumes exactly one liter per unit distance traveled. Moreover, there are *m* gas stations located at various points along the way to the district center. The *i*-th station is located at the point *x*_{i} on the number line and sells an unlimited amount of fuel at a price of *p*_{i} dollars per liter. Find the minimum cost Johnny must pay for fuel to successfully complete the delivery.

Input

The first line of input contains three space separated integers *d*, *n*, and *m* (1 ≤ *n* ≤ *d* ≤ 10^{9}, 1 ≤ *m* ≤ 200 000) — the total distance to the district center, the volume of the gas tank, and the number of gas stations, respectively.

Each of the next *m* lines contains two integers *x*_{i}, *p*_{i} (1 ≤ *x*_{i} ≤ *d* - 1, 1 ≤ *p*_{i} ≤ 10^{6}) — the position and cost of gas at the *i*-th gas station. It is guaranteed that the positions of the gas stations are distinct.

Output

Print a single integer — the minimum cost to complete the delivery. If there is no way to complete the delivery, print -1.

Examples

Input

10 4 4

3 5

5 8

6 3

8 4

Output

22

Input

16 5 2

8 2

5 1

Output

-1

Note

In the first sample, Johnny's truck holds 4 liters. He can drive 3 units to the first gas station, buy 2 liters of gas there (bringing the tank to 3 liters total), drive 3 more units to the third gas station, buy 4 liters there to fill up his tank, and then drive straight to the district center. His total cost is 2·5 + 4·3 = 22 dollars.

In the second sample, there is no way for Johnny to make it to the district center, as his tank cannot hold enough gas to take him from the latest gas station to the district center.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2022 04:31:34 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|