Problem1483--赛车手PIPI

1483: 赛车手PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 95  Solved: 31
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI作为一名赛车手,需要完成从0->1->2->....->n号赛点的拉锯式比赛。赛车每走1个单位距离消耗1个单位的汽油,赛车的油箱的容量是T。
除了终点n以外每个赛点都提供加油服务,但是每个赛点汽油的单价是不同的。赛车在0号点时油箱是空的。
PIPI的驾驶技术是一流的,但是它的预算非常紧张,所以请你计算出完成整个赛程最少的花费是多少?

Input

第一行两个非负整数n,T,分别表示提供加油服务的赛点数,油箱的容量,n<=1e5,T<=1e9.
接下来n行,每行两个整数ai,bi,分别表示从第i个赛点到第i+1个赛点的距离,在第i个赛点的单价。1<=ai,bi<=1e9.

Output

输出走完整个旅程的最小花费,如果无法从起点到达终点输出-1。保证答案不超过long long类型。

Sample Input

3 15
10 2
9 1
8 3

Sample Output

41

Source/Category

中等