补给站

题目背景

一支车队要从营地出发，横穿一条笔直的荒漠公路。公路沿线稀疏地分布着若干补给站，每个站点的油价都不一样。车队的油箱容量有限，队长必须精打细算：在哪个站加油、加多少升，直接决定了这趟行程的花费。

题目描述

公路可以看成一条数轴：营地建在坐标 $0$ 处，目的地建在坐标 $L$ 处。

公路沿线一共有 $n$ 个补给站，第 $i$ 个补给站位于坐标 $x_i$ 处，每升油的价格为 $p_i$ 元。补给站的位置满足 $0 < x_1 < x_2 < \dots < x_n < L$。

油车的油箱容量为 $C$ 升。出发时油箱是满的，所以营地不需要花钱。油车每行驶 $1$ 公里恰好消耗 $1$ 升油；它只能开进补给站加油，而且：

1. 一次加油只能加整数升油，加完之后油箱中的油量不能超过容量 $C$；
2. 行驶过程中油量不能为负，也就是说，从营地到目的地之间的任何时刻，剩余油量都必须足够开到下一个落脚点；
3. 如果某个站点距离上一个落脚点超过 $C$ 公里，那么油车无论如何都开不过去。

请你计算：车队从营地出发、最终抵达目的地，最少需要花多少钱加油。如果无论怎么安排都无法抵达目的地，输出 $-1$。

注意：油车不必在每个补给站都加油，也可以在同一个补给站只加一部分油；油箱里的油可以一直带到后面的站点使用。

输入格式

从标准输入读入数据。

第一行三个整数 $n, C, L$，含义如题面所述。

接下来 $n$ 行，每行两个整数 $x_i, p_i$，依次描述一个补给站的位置与油价。

输出格式

输出到标准输出。

一行一个整数，表示最小加油花费；如果无法抵达目的地，输出 -1。

样例 1 输入

2 5 10
3 5
7 1

样例 1 输出

13

样例 1 解释

出发时油箱里有 $5$ 升油。开到坐标 $3$ 的补给站耗掉 $3$ 升，剩 $2$ 升；在这里加 $2$ 升油，花掉 $2 \times 5 = 10$ 元，油箱重新有 $4$ 升。继续开到坐标 $7$ 的补给站耗掉 $4$ 升，油量为 $0$；在这里加 $3$ 升油，花掉 $3 \times 1 = 3$ 元，正好开到终点。总花费 $10 + 3 = 13$ 元，可以证明没有更便宜的安排。

样例 2 输入

1 3 10
4 1

样例 2 输出

-1

样例 2 解释

唯一的补给站位于坐标 $4$，而满油只能行驶 $3$ 公里，开不到这个站，所以不可能抵达坐标 $10$ 的目的地。

样例 3 输入

2 4 10
3 2
7 2

样例 3 输出

12

样例 3 解释

两个补给站的油价相同，都是 $2$ 元/升（这就是下文特殊性质 A）。整趟行程一共要消耗 $10$ 升油，其中出发时自带的 $4$ 升是免费的，因此至少要买 $10 - 4 = 6$ 升，花费 $6 \times 2 = 12$ 元。油车在坐标 $3$ 处把油箱补满（买 $3$ 升），开到坐标 $7$ 后再买 $3$ 升，正好到达终点，所以 $12$ 元是可以达成的。

特殊性质

本题的数据中存在以下特殊性质，部分测试点会额外满足它们：

• 特殊性质 A：所有补给站的油价都相同，即 $p_1 = p_2 = \dots = p_n$。此时总花费只由总耗油量决定：出发时自带的 $C$ 升免费，所以只要油车能走完全程，答案就是 $(L - C) \times p_1$（若 $L \le C$ 则为 $0$）。
• 特殊性质 B：油价从左到右单调不增，即 $p_1 \ge p_2 \ge \dots \ge p_n$。此时每一站的油都比后面的站更贵，油车只需要“算好能撑到下一站”就可以，不需要反复比较后面所有站点的价格。
• 特殊性质 C：油箱容量足够从营地直接开到目的地，即 $C \ge L$。此时根本不需要加油，只需判断沿路是否有跨不过去的空隙；若没有，答案是 $0$。

数据范围与子任务

对全部测试数据，保证 $1 \le n \le 2 \times 10^5$，$1 \le C \le 10^9$，$2 \le L \le 10^9$，$1 \le p_i \le 10^6$，$0 < x_1 < x_2 < \dots < x_n < L$。

子任务	测试点	分值	$n$	$C, L$	$p_i$	特殊性质
1	$1 \sim 4$	$20$	$\le 2000$	$\le 10^5$	$\le 1000$	无
2	$5 \sim 8$		$\le 5000$	$\le 10^9$	$\le 10^6$
3	$9 \sim 12$		$\le 2 \times 10^5$			A 或 C
4	$13 \sim 20$	$40$				无额外保证

各个子任务的测试点互相独立：不同子任务之间没有先后依赖，只按子任务内的测试点是否全部通过给分。

部分分提示

• 子任务 1 的数据很小，可以直接用 $O(n \cdot C)$ 的 DP 暴力：状态记录“开到第 $i$ 个站、油箱里还剩 $f$ 升油”时的最小花费，枚举在这一站加多少升油。
• 子任务 2 允许 $O(n^2)$ 的做法：每到一站，向后扫描所有站点，找出第一个油价更低的站再决定加油量。
• 子任务 3 有特殊性质 A 或 C：满足 A 时只需判断油车能否走完全程，再输出 $(L - C) \times p_1$（负数取 $0$）；满足 C 时只需判断沿路是否有跨不过去的空隙，能通过则答案是 $0$。
• 子任务 4 需要正解：先用单调栈预处理出“右侧第一个油价严格更低的补给站”，再按“能否开到那个更便宜的站”“是否能加满直接开到终点”分类转移，整体复杂度 $O(n)$。

注意答案可能很大，请使用 $64$ 位整数保存花费。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。