実行時間制限: 1.6 sec / メモリ制限: 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).
小課題
- (5 点) B_i = -1 (1 \leqq i \leqq N).
- (5 点) B_i = -1 または B_i = A_i (1 \leqq i \leqq N).
- (11 点) N \leqq 7.
- (12 点) N \leqq 20.
- (33 点) N \leqq 100.
- (11 点) K = N.
- (23 点) 追加の制約はない.
入力例 1
3 3 1 5 2 3 4 5
出力例 1
5.500000000000000
以下のような順序で選挙活動を行うと,5.5 時間ですべての州の票を獲得することができる.
- 理恵さんが州 2 で 2 時間演説を行い,その州の票を得る.
- 理恵さんが州 2 でさらに 1 時間演説を行い,その州の協力者を得る.
- 理恵さんと協力者 1 人が州 3 で 2 時間演説を行い,その州の票を得る.
- 理恵さんと協力者 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 で 4 時間演説を行い,その州の票を得る.
- 理恵さんが州 2 で 11 時間演説を行い,その州の票を得る.
- 理恵さんが州 3 で 6 時間演説を行い,その州の票を得る.
- 理恵さんが州 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 票を獲得することができる.
- 理恵さんが州 4 で 7 時間演説を行い,その州の票と協力者を得る.
- 理恵さんが州 1 で 4 時間演説を行い,その州の票を得る.同時に,協力者 1 人が州 2 で 4 時間演説を行う.
- 理恵さんと協力者 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 の制約を満たす.