题目描述

小慧在玩一个智力通关游戏，这个游戏有n个关卡，每个关卡需要xi的时间看说明书，需要yi的时间通关。但如果想多次通某个关卡，则只需第一次看说明，后面不用再看说明（即如果想打通第i关t次，则所需时间为xi+t*yi）。

游戏时，必须按次序通关（即只有打通第一关，才能进行第二关，如此类推），求小慧要通m次关的最少时间（可以重复通关）。

输入格式

第一行，两个整数n,m。

接下来n行，每行两个整数xi,yi。

输出格式

输出通关m次所需的最少时间。

样例输入/输出

3 4

3 4

2 3

4 2

18

样例解释

第一次通第一关用7分钟，

第二次通第二关用5分钟，

第三次继续通第二关用3分钟，

第三次继续通第二关用3分钟。

数据规模与提示

对于50%的数据，1<=n,m<=10^4；

对于100%的数据，1<=n,m<=2*10^5, 1<=xi , yi<=10^9