题目描述

牛们收购了一个奶酪工厂,接下来的$\red{N}$个星期里，牛奶价格和劳力价格不断起伏．

第$\red{i}$周，生产一个单位奶酪需要$\red{Ci(1≤}$$\red{Ci≤}$$\red{5000)}$便士．工厂有一个货栈，保存一单位奶酪，每周需要$\red{S(1≤}$$\red{S≤}$$\red{100)}$ 便士，这个费用不会变化．货栈十分强大，可以存无限量的奶酪，而且保证它们不变质．

工厂接到订单，在第$\red{i}$周需要交付$\red{Yi(0≤}$$\red{Yi≤}$$\red{10^4)}$单位的奶酪给委托人．第$\red{i}$周刚生产的奶酪，以及之前的存货，都可以作为产品交付 ．

请帮牛们计算这段时间里完成任务的最小代价．

输入格式

第$\red{1}$行输入两个整数$\red{N}$和$\red{S}$．

接下来$\red{N}$行输入$\red{Ci}$和$\red{Yi}$．

输出格式

输出最少的代价．注意，可能超过$\red{32}$位长整型．

样例

输入样例

4 5
88 200
89 400
97 300
91 500

输出样例

126900

提示

第$\red{1}$周生产$\red{200}$单位奶酪并全部交付；

第$\red{2}$周生产$\red{700}$单位，交付$\red{400}$单位，有$\red{300}$单位；

第$\red{3}$周交 付$\red{300}$单位存货．

第$\red{4}$周生产并交付$\red{500}$单位．