配点: 1000 点
問題文
ALGO 街道是一条全长 L 公里的直线道路。街道的一端作为起点,另一端作为终点。
这条街道上有 N 个加油站。i 個目 (1 \leq i \leq N) 个加油站从起点开始 A_i 公里处,价格为 1 每升 C_i 这是日元。
油耗为 1 km/L,最大可加 K 升汽油的车辆,判断是否可以从起点到达终点,如果可以的话,请求出最少需要多少日元的汽油费用的程序。
但假设在开始时油箱是满的。此外,当油量正好为 0 假设在燃油达到某升数时,可以在加油站加油或到达终点。
制約
- 0 \leq N \leq 700000
- 1 \leq K \leq L \leq 700000
- 1 \leq A_1 \leq A_2 \leq \dots \leq A_N \leq L - 1
- 1 \leq C_i \leq 10^{12}
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N L K A_1 C_1 A_2 C_2 \vdots A_N C_N
出力
请在行中输出从起点到终点所需的最少汽油费用。 1 但是,如果从起点到终点无法到达,请改为 -1 。
部分点
在这个问题中,N \leq 100, L \leq 100 对满足 的所有情况回答正确的话,可以获得部分分数 500 赚取积分。
入力例 1
3 11 4 4 70 6 50 9 100
出力例 1
440
如下图所示加油是最优的。在加油站 1, 2, 3 分别 2, 4, 1 升加油,因此汽油费用为 70 \times 2 + 50 \times 4 + 100 \times 1 = 440 是日元。

入力例 2
1 100 60 39 1
出力例 2
-1
即使在加油站 1 将车加满油,从出发地到 99 公里处汽油就会耗尽,无法到达终点。
入力例 3
6 100 30 19 1700000000 44 1400000000 44 1900000000 57 1600000000 78 1300000000 91 1500000000
出力例 3
100800000000