问题文

工厂里有 $N$ 台制作礼物的机器。第 $i(1≦i≦N)$ 台机器最初需要 $a_i$ 秒钟来制作一个礼物。
然而，每制作一个礼物，该机器的性能就会下降，制作一个礼物所需的时间会增加 $b_i$ 秒。
因此，第 $i(1≦i≦N)$ 台机器制作第 $s_i$ 个礼物需要 $a_i + (s_i-1)×b_i$ 秒。
另外，由于工厂供电不足，不能同时运行多台机器。

Dolphin 希望在尽可能短的时间内制作 $K$ 个礼物。
请计算制作所有礼物所需的最小总时间。

制约条件

• $1≦N≦10^5$
• $1≦K≦10^5$
• $1≦a_i≦10^9$
• $0≦b_i≦10^9$
• 输入均为整数。

输入

输入以以下格式从标准输入中给出:

$N$ $K$ $a_1$ $b_1$ $:$ $a_N$ $b_N$

输出

输出制作所有礼物所需的最小总时间。

输入示例 1

3 3
1 3
2 0
3 4

输出示例 1

5

最短时间内制作 $3$ 个礼物的方式是按以下次数操作工厂里的机器，总共用时 $5$ 秒钟：

• 第一台机器：$1$ 次
• 第二台机器：$2$ 次
• 第三台机器：$0$ 次

输入示例 2

10 100000
22 59
26 60
72 72
47 3
97 16
75 41
82 77
17 97
32 32
28 7

输出示例 2

7521307799

请注意溢出。

输入示例 3

1 100000
1000000000 1000000000

输出示例 3

5000050000000000000