暂无测试数据。

Description

Jim是一个胆小的男生，可是每天他都要学习到很晚才能回家，而且他回家的路上没有路灯。Jim非常怕黑，万幸的是他还有一个手电筒可以用，我们设手电筒的电量上限为\(T\)。在Jim回家的路上有\((N+1)\)个充电站，\(0\)是起点\(N\)是终点，Jim每走一个单位距离消耗\(1\)个单位的电量.给出每个充电站到下一个充电站的距离\(D\)，以及冲单位电量的花费\(P\)，求整个旅途的最少花费。如果Jim无法保证全程手电筒都亮着输出\(-1\).

Format

Input

第1行：2个数\(N, T\)中间用空格分隔，\(N + 1\)为充电站的数量，\(T\)为手电筒的电池容量\( (2 ≤ N ≤ 500000,1≤T≤10^9) \)。
第2至N + 1行：每行\(2\)个数\(D[i]\), \(P[i]\)，中间用空格分隔，分别表示到下一个充电站的距离和充电的
单价\((1≤D[i], P[i]≤1000000)\)。

Output

输出走完整个旅程的最小花费，如果无法保证手电筒全程照亮，输出\(-1\)

Sample 1

Input

3 15
10 2
9 1
8 3

Output

41

Limitation

1s, 256MiB for each test case.

Hint

样例解释

\(D = \{10, 9, 8\}\), \(P = \{2, 1, 3\}\)，\(T = 15\)，最小花费为\(41\)：在\(0\)冲\(10\)个单位的电，在\(1\)冲\(15\)个单位的电，在\(2\)冲\(2\)个单位的电，刚好到家用完所有的电。

数据范围

对于30%的数据 \(N \leq 50\)
对于100%的数据 \(N \leq 500000\)

Source

CSP 2019 模拟测试题（三）