C - 選挙で勝とう (Let's Win the Election) Editorial /

Time Limit: 1.6 sec / Memory Limit: 1024 MB

配点： 100 点

JOI 国は N 個の州からなり，それぞれ 1 から N までの番号が付けられている．2022 年，JOI 国では大統領選挙が開催されることになった．この選挙では各州で投票が行われ，勝った候補者がその州に割り当てられている 1 票を獲得する．

さて，大統領選挙に出馬する理恵さんは，演説によって自身への信頼度を上げ，選挙で勝とうと考えた．演説により，具体的には次のことが起こる．

  • 州 i (1 \leqq i \leqq N) での合計演説時間が A_i 時間に達すると，その州に割り当てられている 1 票を獲得できる．
  • 州 i (1 \leqq i \leqq N) での合計演説時間が B_i 時間に達すると，協力者 1 人を得ることができる．得られた協力者は，それ以降演説を行い，合計演説時間を増やすことができる．
  • ただし，州 i からの協力者を得られない場合もあり，その場合は B_i = -1 として情報が与えられる．それ以外の場合は，B_i \geqq A_i であることが保証される．

なお，州 i (1 \leqq i \leqq N) で獲得した協力者が州 i 以外で演説をすることや，1 つの州で同時に 2 人以上が演説をすることも可能である．たとえば，ある州で同時に 2 人が x 時間演説をした場合，この州の合計演説時間は 2x 時間増加する．ただし，演説時間が整数である必要はない．また，州の間を移動する時間は無視できるものとする．

投票日が近いので，理恵さんは目標の K 票をできるだけ早く獲得したい．

州の数と各州の情報が与えられたとき，K 票を集めるまでにかかる時間の最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

N
K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

標準出力に，K 票を集めるまでにかかる時間の最小値を 1 行で出力せよ．正解との絶対誤差が 0.01 以下であるような答えを出力すれば，正答とみなされる．出力は以下のいずれかの形式でなければならない．

  • 整数．（例：123，0，-2022）
  • 整数，半角ピリオド，0 から 9 までの数字を並べた列，をその順にスペースなどで区切らず続けた形式．出力する小数点以下の桁数に制限はない．（例：123.4，-123.00，0.00288）

たとえば，1.23456e+05 や 1.23456e5 のような指数表記で出力してはならない．

制約

  • 1 \leqq N \leqq 500．
  • 1 \leqq K \leqq N．
  • 1 \leqq A_i \leqq 1\,000 (1 \leqq i \leqq N)．
  • A_i \leqq B_i \leqq 1\,000 または B_i = -1 (1 \leqq i \leqq N)．

小課題

  1. (5 点) B_i = -1 (1 \leqq i \leqq N)．
  2. (5 点) B_i = -1 または B_i = A_i (1 \leqq i \leqq N)．
  3. (11 点) N \leqq 7．
  4. (12 点) N \leqq 20．
  5. (33 点) N \leqq 100．
  6. (11 点) K = N．
  7. (23 点) 追加の制約はない．

入力例 1

3
3
1 5
2 3
4 5

出力例 1

5.500000000000000

以下のような順序で選挙活動を行うと，5.5 時間ですべての州の票を獲得することができる．

  1. 理恵さんが州 2 で 2 時間演説を行い，その州の票を得る．
  2. 理恵さんが州 2 でさらに 1 時間演説を行い，その州の協力者を得る．
  3. 理恵さんと協力者 1 人が州 3 で 2 時間演説を行い，その州の票を得る．
  4. 理恵さんと協力者 1 人が州 1 で 0.5 時間演説を行い，その州の票を得る．

この入力例は小課題 3, 4, 5, 6, 7 の制約を満たす．

入力例 2

7
4
4 -1
11 -1
6 -1
12 -1
36 -1
11 -1
20 -1

出力例 2

32.000000000000000

以下のような順序で選挙活動を行うと，32 時間で 4 票を獲得することができる．

  1. 理恵さんが州 1 で 4 時間演説を行い，その州の票を得る．
  2. 理恵さんが州 2 で 11 時間演説を行い，その州の票を得る．
  3. 理恵さんが州 3 で 6 時間演説を行い，その州の票を得る．
  4. 理恵さんが州 6 で 11 時間演説を行い，その州の票を得る．

この入力例は小課題 1, 2, 3, 4, 5, 7 の制約を満たす．

入力例 3

5
3
4 -1
5 -1
6 -1
7 7
8 8

出力例 3

11.500000000000000

以下のような順序で選挙活動を行うと，11.5 時間で 3 票を獲得することができる．

  1. 理恵さんが州 4 で 7 時間演説を行い，その州の票と協力者を得る．
  2. 理恵さんが州 1 で 4 時間演説を行い，その州の票を得る．同時に，協力者 1 人が州 2 で 4 時間演説を行う．
  3. 理恵さんと協力者 1 人が州 2 で 0.5 時間演説を行い，その州の票を得る．

この入力例は小課題 2, 3, 4, 5, 7 の制約を満たす．

入力例 4

7
5
28 36
11 57
20 35
19 27
31 33
25 56
38 51

出力例 4

62.166666666666664

この入力例は小課題 3, 4, 5, 7 の制約を満たす．

入力例 5

20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260

出力例 5

644.203571428571422

この入力例は小課題 4, 5, 7 の制約を満たす．

Source Name

JOI 2021/2022 本選 問題3