题目描述

小慧在玩一个智力通关游戏，这个游戏有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。