题目描述
FarmerJhon决定去一次跨国旅游度假。为了不让他的奶牛们感到被抛弃,他决定租一辆大卡车来带他的奶牛们一起旅行。
这辆卡车有一个很大的油箱,可以装下G个单位的油(1<=G<=1,000,000),不幸的是,卡车的耗油量也很大,卡车每运动一个单位的距离,就要消耗一个单位的油。FarmerJhon要在他 的旅程中走D个单位的距离。(1<=D<=1,000,000,000)
因为FJ直到他可能要几次在旅途中停下,给油箱加油,所以他把在旅途沿路上的N个加油站的记录做成了表格。对于第i个加油站,他记录了加油站与起点的距离Xi(0<=Xi<=D),以及加油站中每单位油的价格Yi(1<=Yi<=1,000,000)。
已知以上所给的信息,以及FJ在路途中实际使用的油的数量B(0<=B<=D),请计算出FJ到达目的地时花费的油费用的最小值。如果FJ无法到达旅途的终点,那么轻输出−1。本题的答案可能无法使用32位整数储存。
输入格式
第1行: 四个整数: N,G,B,D
第2~1+N行: 每一行都有两个整数Xi与Yi,意义如上所述
输出格式
一个整数,如果FJ无法到达旅途的终点,那么输出−1,否则输出FJ到达目的地时花费的油费用的最小值。
样例
输入样例
4 10 3 17
2 40
9 15
5 7
10 12
输出样例
174
提示
样例解释:FJ先移动2个单位,然后停下购买2个单位的油(要花费40×20)。然后一直前进到距离起点5个单位的地方,此时油箱为空。这时向油箱里加满油(要花费7×10)。再向前走5个单位,加2个单位的油(花费12×2)。最后一直走到终点。此时总花费是174.