C - Factory

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

工場にプレゼントを作る機械が 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