AT_code_thanks_festival_2017_c Factory

[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2017/tasks/code_thanks_festival_2017_c 工場にプレゼントを作る機械が $ 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 $ 個をできる限り短い時間で製造したいです。 プレゼントの製造にかかる最小の合計時間を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ a_1 $ $ b_1 $ $ : $ $ a_N $ $ b_N $

プレゼントの製造にかかる最小の合計時間を出力せよ。

### 制約 - $ 1≦N≦10^5 $ - $ 1≦K≦10^5 $ - $ 1≦a_i≦10^9 $ - $ 0≦b_i≦10^9 $ - 入力は全て整数である。 ### Sample Explanation 1 工場にある機械を以下の回数で動かしたとき、$ 5 $ 秒で $ 3 $ 個のプレゼントを作ることができます。 - $ 1 $ 番目の機械: $ 1 $ 回 - $ 2 $ 番目の機械: $ 2 $ 回 - $ 3 $ 番目の機械: $ 0 $ 回 ### Sample Explanation 2 オーバーフローに注意してください。