← 返回题目列表

AtCoder · code_thanks_festival_2017_c

C. 工厂

中文机器翻译题面 查看原题

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