6474: USACO 2013 US Open, Silver —— Problem 2. Fuel Economy
[Creator : ]
Description
Farmer John has decided to take a cross-country vacation. Not wanting his cows to feel left out, however, he has decided to rent a large truck and to bring the cows with him as well!
The truck has a large tank that can hold up to $G\ (1 \leq G \leq 1,000,000)$ units of fuel. Unfortunately, it gets very poor mileage: it consumes one unit of fuel for every unit of distance traveled, and FJ has a total of $D\ (1 \leq D \leq 1,000,000,000)$ units of distance to travel along his route.
Since FJ knows he will probably need to stop to refill his tank several times along his trip, he makes a list of all the $N\ (1 \leq N \leq 50,000)$ fuel stations along his route. For each station $i$, he records its distance $X_i\ (0 \leq X_i \leq D)$ from the start of the route, as well as the price $Y_i\ (1 \leq Y_i \leq 1,000,000)$ per unit of fuel it sells.
Given this information, and the fact that FJ starts his journey with exactly $B\ (0 \leq B \leq D)$ units of fuel, please determine the minimum amount of money FJ will need to pay for fuel in order to reach his destination. If it is impossible for him to reach the destination, please output $-1$. Note that the answer to this problem may not fit into a standard $32$-bit integer.
Farmer Jhon 决定去一次跨国旅游度假。为了不让他的奶牛们感到被抛弃，他决定租一辆大卡车来带他的奶牛们一起旅行。
这辆卡车有一个很大的油箱，可以装下 $G$ 个单位的油，不幸的是，卡车的耗油量也很大，卡车每运动一个单位的距离，就要消耗一个单位的油。Farmer Jhon 要在他的旅程中走 $D$ 个单位的距离。
因为 FJ 直到他可能要几次在旅途中停下，给油箱加油，所以他把在旅途沿路上的 $N$ 个加油站的记录做成了表格。对于第 $i$ 个加油站，他记录了加油站与起点的距离 $X_i$，以及加油站中每单位油的价格 $Y_i$。
已知以上所给的信息，以及 FJ 在路途中实际使用的油的数量 $B$，请计算出 FJ 到达目的地时花费的油费用的最小值。如果 FJ 无法到达旅途的终点，那么轻输出 $-1$。本题的答案可能无法使用 $32$ 位整数储存。
The truck has a large tank that can hold up to $G\ (1 \leq G \leq 1,000,000)$ units of fuel. Unfortunately, it gets very poor mileage: it consumes one unit of fuel for every unit of distance traveled, and FJ has a total of $D\ (1 \leq D \leq 1,000,000,000)$ units of distance to travel along his route.
Since FJ knows he will probably need to stop to refill his tank several times along his trip, he makes a list of all the $N\ (1 \leq N \leq 50,000)$ fuel stations along his route. For each station $i$, he records its distance $X_i\ (0 \leq X_i \leq D)$ from the start of the route, as well as the price $Y_i\ (1 \leq Y_i \leq 1,000,000)$ per unit of fuel it sells.
Given this information, and the fact that FJ starts his journey with exactly $B\ (0 \leq B \leq D)$ units of fuel, please determine the minimum amount of money FJ will need to pay for fuel in order to reach his destination. If it is impossible for him to reach the destination, please output $-1$. Note that the answer to this problem may not fit into a standard $32$-bit integer.
Farmer Jhon 决定去一次跨国旅游度假。为了不让他的奶牛们感到被抛弃，他决定租一辆大卡车来带他的奶牛们一起旅行。
这辆卡车有一个很大的油箱，可以装下 $G$ 个单位的油，不幸的是，卡车的耗油量也很大，卡车每运动一个单位的距离，就要消耗一个单位的油。Farmer Jhon 要在他的旅程中走 $D$ 个单位的距离。
因为 FJ 直到他可能要几次在旅途中停下，给油箱加油，所以他把在旅途沿路上的 $N$ 个加油站的记录做成了表格。对于第 $i$ 个加油站，他记录了加油站与起点的距离 $X_i$，以及加油站中每单位油的价格 $Y_i$。
已知以上所给的信息，以及 FJ 在路途中实际使用的油的数量 $B$，请计算出 FJ 到达目的地时花费的油费用的最小值。如果 FJ 无法到达旅途的终点，那么轻输出 $-1$。本题的答案可能无法使用 $32$ 位整数储存。
Input
第1行： 四个整数：$N,G,B,D$
第 $2 \sim N+1$ 行： 每一行都有两个整数 $X_i$ 与 $Y_i$，意义如上所述。
第 $2 \sim N+1$ 行： 每一行都有两个整数 $X_i$ 与 $Y_i$，意义如上所述。
Output
一个整数，如果 FJ 无法到达旅途的终点，那么输出 $-1$，否则输出 FJ 到达目的地时花费的油费用的最小值。
Sample 1 Input
4 10 3 17
2 40
9 15
5 7
10 12
Sample 1 Output
174
FJ 先移动 $2$ 个单位，然后停下购买 $2$ 个单位的油（要花费 $40 \times 20$）。然后一直前进到距离起点 $5$ 个单位的地方，此时油箱为空。这时向油箱里加满油（要花费 $7 \times 10$）。再向前走 $5$ 个单位，加 $2$ 个单位的油（花费 $12 \times 2$）。最后一直走到终点。此时总花费是 $174$。