問題文

工場にプレゼントを作る機械が $N$ 台あります。$i(1≦i≦N)$ 番目の機械は、最初 $a_i$ 秒でプレゼントを $1$ 個作れます。
しかし、ある機械でプレゼントを $1$ 個作るたびにその機械のみが劣化して、プレゼントを $1$ 個作るのにかかる時間が $b_i$ 秒増えます。
したがって、$i(1≦i≦N)$ 番目の機械で $s_i$ 個目のプレゼントを作るのに　$a_i + (s_i-1)×b_i$ 秒かかります。
また、工場に供給される電力が少ないため、複数の機械を同時に動かすことはできません。

イルカはプレゼント $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

工場にある機械を以下の回数で動かしたとき、$5$ 秒で $3$ 個のプレゼントを作ることができます。

• $1$ 番目の機械: $1$ 回
• $2$ 番目の機械: $2$ 回
• $3$ 番目の機械: $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