A10201 | Package Delivery

Johnny 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.

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.

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