← 返回题目列表

AtCoder · tessoku_book_fq

C19. 汽油优化问题

中文机器翻译题面 查看原题

配点: 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