解题思路

这题本质是一个经典的“最小费用加油”问题，使用贪心算法即可。

已知：

• 出发点在距离为 $0$ 的位置，初始电量是满的，可直接行驶 $C$ 公里
• 第 $i$ 个充电站在位置 $d_i$，单价为 $p_i$
• 每走 $1$ 公里消耗 $1$ 单位电量

题目内容

多多驾驶电动车从起点$0$出发，目的地距离为$L$公里。电动车满电时可行驶$C$公里，即电池容量为$C$公里续航。沿途有$n$个充电站，第$i$个充电站位于距离起点$d$公里处，充电价格一公里$p_i$

多多可以在任何充电站进行充电，充电量可以任意，但不能超过电池总容量

已知多多出发时电池处于满电状态。请你帮多多规划充电策略，求出到达目的地所需的最少充电费用。如果无论如何都无法到达目的地，请输出$-1$。

输入描述

第一行包含三个整数$L,C,n$别表示目的地距离、满电续航公里数、充电站的数量。$(1<=L<=1e9,1<=C<=1e9,1<=n<= 5000)$

接下来$n$行，每行包含两个整数$d,p$，分别表示第$i$个充电站距离起点的距离以及该站的充电单价。$(1<=d_i≤ d_{i+1}<L,1<=p_i<=1e9)$

输出描述

输出一个整数，表示到达目的地所需的最少充电总费用。如果无法到达，输出$-1$。

样例1

输入

20 10 3
4 5
9 2
15 6

输出

24

说明

起点满电(续航$10$)

开至距离$9$的充电站，此时剩余电量$1$

在距离$9$的充电站充$9$公里电量达到满电，花费$9*2=18$，此时电量$10$

开至距离$15$的充电站，消耗$6$，此时剩余电量$4$。

在距离$15$的充电站充$1$公里电量，花费$1*6=6$，此时电量$5$。

刚好开到终点$20$(消耗$5$)，剩余电量$0$.

总费用: $18+6=24$

样例2

输入

20 5 1
10 5

输出

-1

说明

满电只能跑$5$公里，还没跑到第一个充电站就没电了，所以无法到达。