AT_joi2022ho_c 選挙で勝とう (Let's Win the Election)

[problemUrl]: https://atcoder.jp/contests/joi2022ho/tasks/joi2022ho_c 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 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 以下のような順序で選挙活動を行うと，$ 5.5 $ 時間ですべての州の票を獲得することができる． 1. 理恵さんが州 $ 2 $ で $ 2 $ 時間演説を行い，その州の票を得る． 2. 理恵さんが州 $ 2 $ でさらに $ 1 $ 時間演説を行い，その州の協力者を得る． 3. 理恵さんと協力者 $ 1 $ 人が州 $ 3 $ で $ 2 $ 時間演説を行い，その州の票を得る． 4. 理恵さんと協力者 $ 1 $ 人が州 $ 1 $ で $ 0.5 $ 時間演説を行い，その州の票を得る． この入力例は小課題 $ 3,\ 4,\ 5,\ 6,\ 7 $ の制約を満たす． - - - - - - ### Sample Explanation 2 以下のような順序で選挙活動を行うと，$ 32 $ 時間で $ 4 $ 票を獲得することができる． 1. 理恵さんが州 $ 1 $ で $ 4 $ 時間演説を行い，その州の票を得る． 2. 理恵さんが州 $ 2 $ で $ 11 $ 時間演説を行い，その州の票を得る． 3. 理恵さんが州 $ 3 $ で $ 6 $ 時間演説を行い，その州の票を得る． 4. 理恵さんが州 $ 6 $ で $ 11 $ 時間演説を行い，その州の票を得る． この入力例は小課題 $ 1,\ 2,\ 3,\ 4,\ 5,\ 7 $ の制約を満たす． - - - - - - ### Sample Explanation 3 以下のような順序で選挙活動を行うと，$ 11.5 $ 時間で $ 3 $ 票を獲得することができる． 1. 理恵さんが州 $ 4 $ で $ 7 $ 時間演説を行い，その州の票と協力者を得る． 2. 理恵さんが州 $ 1 $ で $ 4 $ 時間演説を行い，その州の票を得る．同時に，協力者 $ 1 $ 人が州 $ 2 $ で $ 4 $ 時間演説を行う． 3. 理恵さんと協力者 $ 1 $ 人が州 $ 2 $ で $ 0.5 $ 時間演説を行い，その州の票を得る． この入力例は小課題 $ 2,\ 3,\ 4,\ 5,\ 7 $ の制約を満たす． - - - - - - ### Sample Explanation 4 この入力例は小課題 $ 3,\ 4,\ 5,\ 7 $ の制約を満たす． - - - - - - ### Sample Explanation 5 この入力例は小課題 $ 4,\ 5,\ 7 $ の制約を満たす．