问题

工厂里有 $N$ 台做礼物的机器。一开始第 $i$ 台机器可以花 $a_i$ 秒时做出一份礼物。

然而每一次制作礼物，制作礼物的那台机器零件会被磨损，因此制作一份礼物所需的时间会增加 $b_i$ 秒。

于是易得：你需要 $a_i + (s_i - 1) \cdot b_i$ 秒才能在第 $i$ 台机器上制作第 $s_i$ 次礼物。（$s_i$ 表示在第 $i$ 台机器上制作礼物的次数）

另外由于工厂的供电量小，你无法同时运行多台机器。

请你找出制作 $K$ 个礼物所需的最少总时间。

输入输出格式

输入

第一行输入两个正整数 $N, K$, 表示机器数目与总共需制作的礼物数量。

接下来 $N$ 行，第 $i$ 行输入两个数 $A_i, B_i(1 \leq A_i \leq 10^9, 0 \leq B_i \leq 10^9)$, 对应题目描述中的 $a_i, b_i$.

输出

对于每一个用例，都输出一个整数，表示制作 $K$ 个礼物所需的最小总用时。