#2145. Fuel Economy

Fuel Economy

题目描述

FarmerJhon\red{Farmer Jhon }决定去一次跨国旅游度假。为了不让他的奶牛们感到被抛弃,他决定租一辆大卡车来带他的奶牛们一起旅行。

这辆卡车有一个很大的油箱,可以装下G\red{G}个单位的油(1<=G<=1,000,000),\red{(1 <= G <= 1,000,000), }不幸的是,卡车的耗油量也很大,卡车每运动一个单位的距离,就要消耗一个单位的油。FarmerJhon\red{Farmer Jhon }要在他 的旅程中走D\red{D}个单位的距离。(1<=D<=1,000,000,000)\red{(1 <= D <= 1,000,000,000)}

因为FJ\red{FJ}直到他可能要几次在旅途中停下,给油箱加油,所以他把在旅途沿路上的N\red{N}个加油站的记录做成了表格。对于第i\red{i}个加油站,他记录了加油站与起点的距离Xi(0<=Xi<=D),\red{X_i(0 <= X_i <= D),}以及加油站中每单位油的价格Yi(1<=Yi<=1,000,000)\red{Y_i(1 <= Y_i <= 1,000,000)}

已知以上所给的信息,以及FJ\red{FJ}在路途中实际使用的油的数量B(0<=B<=D)\red{B(0 <= B <= D),}请计算出FJ\red{FJ}到达目的地时花费的油费用的最小值。如果FJ\red{FJ}无法到达旅途的终点,那么轻输出1\red{-1}。本题的答案可能无法使用32\red{32}位整数储存。

输入格式

1\red{1}行: 四个整数: N,G,B,D\red{N,G,B,D}

2\red{2}~1+N\red{1+N}行: 每一行都有两个整数Xi\red{X_i}Yi\red{Y_i,}意义如上所述

输出格式

一个整数,如果FJ\red{FJ}无法到达旅途的终点,那么输出1\red{-1,}否则输出FJ\red{FJ}到达目的地时花费的油费用的最小值。

样例

输入样例

4 10 3 17
2 40
9 15
5 7
10 12

输出样例

174

提示

样例解释:FJ\red{FJ}先移动2\red{2}个单位,然后停下购买2\red{2}个单位的油(要花费40×20\red{40 \times20)}。然后一直前进到距离起点5\red{5}个单位的地方,此时油箱为空。这时向油箱里加满油(要花费7×10\red{7\times 10)}。再向前走5\red{5}个单位,加2\red{2}个单位的油(花费12×2\red{12\times 2)}。最后一直走到终点。此时总花费是174\red{174}.