Допомога-або-інакше#3049

Допомога-або-інакше

1 секунда

64 мегабайти

Легка

В одній з колоній для фінансистів незабаром відбудеться щорічна подія з громадських робіт, з правилами, що відповідають цьому місцю. Кожному ув'язненому призначають множину $P$ з $N$ людей, яким треба допомогти з фінансами, а також обмеження часу $K$ хвилин. Для кожної людини $j$ ( $1 \leq j \leq N$ 1 \leq j \leq N) ув'язненому повідомляють штрафний час $e_{j}$ e_j за ненадання допомоги та тривалість $d_{j}$ d_j хвилин, необхідних для допомоги. Громадські роботи починаються з часу $T = 0$ T=0. Якщо ув'язнений починає допомагати людині $j$ у момент часу $T$ , він повинен завершити цю допомогу до $T + d_{j}$ T+d_j. Незалежно від якості консультації та моменту завершення, $C_{j} (= T + d_{j})$ C_j (=T+d_j) віднімається з дозволеного часу ув'язненого. Поки не закінчено роботу над $j$ (до $T + d_{j}$ T+d_j), не можна братися за іншу людину. Якщо $S$ — множина людей, яким допомогли, то загальна кількість використаних хвилин — це сума всіх $C_{j}$ C_j для тих, кому допомогли.

Ваша задача — написати програму, що обчислює максимальну кількість людей, яким ув'язнений може допомогти, не перевищуючи ліміту в $K$ хвилин.

Вхідні дані

Вхід складається з декількох наборів для різних ув'язнених. Опис кожного ув'язненого починається з двох цілих чисел $N$ та $K$ , розділених пропуском, де $N$ — кількість людей, а $K$ — максимальна дозволена кількість хвилин. $0 < N \leq 200$ 0 < N \leq 200 та $0 < K \leq 6000$ 0 < K \leq 6000. Кожен з наступних $N$ рядків містить по два цілих числа, розділених пропуском, які відповідають штрафу та тривалості для однієї людини. Всі числа — від $0$ до $10000$ включно. Вхід завершують рядком із двох нулів.

Вихідні дані

Для кожного ув'язненого виведіть в окремому рядку максимальну кількість людей, яким вдасться допомогти, не перевищивши ліміту часу. Якщо жодній людині допомогти не вдасться, виведіть Mission Impossible.

Приклади

Приклад 1