暂无测试数据。

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 模拟测试题（三）