题目描述

在神话时代的“智慧迷宫”中，存在着一个由无数谜题构成的古老挑战。这个迷宫有n个房间，每个房间代表一个关卡，每个关卡背后都隐藏着古老的智慧和秘密。只有真正具有洞察力和策略的人，才能解开这些谜题并深入迷宫的更深处。

在这个迷宫中，有一位年轻的探险者，名叫莱恩。莱恩拥有着对谜题的热情和解决问题的天赋。他的目标是通过m次任意关卡，并且用时最少，以期获得迷宫中最宝贵的智慧。

莱恩知道，每个房间的谜题首次解开需要阅读说明书的时间$𝑥_𝑖$，以及解开谜题本身所需的时间$𝑦_𝑖$。如果莱恩想要重复解开同一个房间的谜题，他只需第一次阅读说明书，之后每次解开将不再需要额外的时间(即如果想解开第i个房间t次谜题，则所需时间为$x_i$+t*$y_i$)。

输入格式：

第一行，两个整数n,m。 接下来n行，每行两个整数$𝑥_𝑖$,$𝑦_𝑖$。

输出格式：

输出解开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<=$x_i$ , $y_i$<=$10^9$