配点 : 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