問題文

工場にプレゼントを作る機械が 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
• 入力は全て整数である。

入力例 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