题目描述

小婷要连续生产 $N$ 周。第 $i$ 周每件产品当周生产成本为 $C_i$，需求为 $Y_i$ 件。产品可提前生产并保存，每保存一周每件增加 $S$ 的费用。求满足全部需求的最小总费用。

输入格式

第一行 $N,S$，接下来 $N$ 行为 $C_i,Y_i$。

输出格式

输出最小总费用。

输入

6 91
1998 3633
1249 7982
4025 1999
2786 1889
4775 678
1243 222

输出

23917933

输入

8 49
2641 8201
585 7611
1972 3216
3499 9802
2397 4523
1449 3522
1723 8591
3321 5875

输出

53201159

输入

40 32
4278 8617
4077 2494
4331 3551
947 9072
1771 6137
1672 2589
3747 5296
4418 4014
1229 9926
2990 417
1055 3456
3998 7180
1280 3590
4145 9505
4155 7752
1689 2228
1972 6840
4076 6856
3684 2366
268 4763
4357 6446
3196 3346
1964 7495
2227 9073
2139 8044
3495 204
2618 3800
2979 7975
3189 672
2828 3479
990 8766
4262 663
2726 8863
3932 3765
4642 8939
1598 9553
305 889
3706 2754
4908 9737
1894 3076

输出

216262515

数据范围

$1\le N\le10^4$，$1\le C_i\le5000$，$1\le S\le100$，$0\le Y_i\le10^4$。