走夜路

暂无测试数据。

Description

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

Format

Input

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

Output

输出走完整个旅程的最小花费,如果无法保证手电筒全程照亮,输出1-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}D = \{10, 9, 8\}, P={2,1,3}P = \{2, 1, 3\}T=15T = 15,最小花费为4141:在001010个单位的电,在111515个单位的电,在2222个单位的电,刚好到家用完所有的电。

数据范围

对于30%的数据 N50N \leq 50
对于100%的数据 N500000N \leq 500000

Source

CSP 2019 模拟测试题(三)

信息

ID
1019
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者