Farmer John 决定去一次跨国旅游度假。为了不让他的奶牛们感到被抛弃,他决定租一辆大卡车来带他的奶牛们一起旅行。
这辆卡车有一个很大的油箱,可以装下 G 个单位的油(1 \le G \le {10}^6),不幸的是,卡车的耗油量也很大,卡车每运动一个单位的距离,就要消耗一个单位的油。Farmer John 要在他的旅程中走 D 个单位的距离(1 \le D \le {10}^9)。
因为 FJ 知道他可能要几次在旅途中停下,给油箱加油,所以他把在旅途沿路上的 N(1\le N\le 5\times 10^4)个加油站的记录做成了表格。对于第 i 个加油站,他记录了加油站与起点的距离 X_i(0 \le X_i \le D),以及加油站中每单位油的价格 Y_i(1 \le Y_i \le {10}^6)。
已知以上所给的信息,以及 FJ 在路途开始时拥有的燃油的数量 B(0 \le B \le D),请计算出 FJ 到达目的地时花费的油费用的最小值。如果 FJ 无法到达旅途的终点,那么请输出 -1。本题的答案可能无法使用 32 位整数储存。