Package Delivery

题意翻译

# 题目描述 $Johnny$驾驶着他的~~山寨牌~~卡车。他必须从他的家乡去城区中心送一个物件。假设他家的位置在数轴上的原点$O$，城区中心在点$D$。 $Johnny$的卡车有一个油箱~~（废话，哪个车子发动不需要油的，当然除了电动车）~~最多可以装$N$升汽油，出发时，他的油箱里装满了汽油。当$Johnny$驾驶卡车时，每行驶$1$个单位长度会消耗$1L$油。当然，在行驶的途中，有$M$个加油站，第$i$个加油站在数轴上表示$x_i$的位置，并且每加$1L$油，要付$p_i$美元的油钱。 $Johnny$想知道，要完美完成接送任务，需要花多少$Dollar?$ # 输入输出格式 ## 输入 第一行输入$D$，$N$和$M$（$1<=N<=D<=10^9$）。 接下来$M$行，一行代表加油站的位置$x_i$和单价$p_i$。 ## 输出 输出仅一行，代表最少花费。

题目描述

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.

输入输出样例

输入样例 #1

10 4 4
3 5
5 8
6 3
8 4

输出样例 #1

22

输入样例 #2

16 5 2
8 2
5 1

输出样例 #2

-1

说明

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.