Допомога-або-інакше
У виправній колонії для фінансових спеціалістів незабаром відбудеться щорічний захід з громадських робіт, організований за певними правилами, що підходять для колонії. Кожному ув'язненому призначається набір P з N осіб, яким він повинен допомогти з їхніми фінансами, та ліміт часу в K хвилин. Для кожної з j-ї особи, 1 ≤ j ≤ N, ув'язненому повідомляється штрафний час e_j за відмову від допомоги та тривалість d_j хвилин, необхідна для надання допомоги. Ув'язнений починає свою роботу в момент часу T, що дорівнює нулю. Якщо ув'язнений почав допомагати j-й особі в момент часу T, він повинен завершити роботу не пізніше T+d_j. Незалежно від якості поради та часу завершення, значення C_j ( = T+ d_j ) віднімається з виділеного часу. Також ув'язненому не дозволяється працювати з іншою особою до часу T+d_j. Якщо S — це набір осіб, яким допоміг ув'язнений, то загальна кількість використаних хвилин розраховується як сума всіх C_j.
Ваше завдання — написати програму, яка обчислює максимальну кількість осіб, яким ув'язнений може допомогти, не перевищуючи ліміт у K хвилин.
Вхідні дані
Вхід складається з наборів даних для кількох ув'язнених. Опис для кожного ув'язненого починається з двох цілих чисел N і K, розділених пробілом на окремому рядку, які представляють кількість осіб і максимально допустиму кількість хвилин. 0 < N ≤ 200 і 0 < K ≤ 6000. Кожен з наступних N рядків містить два цілі числа, розділені пробілом, які представляють штраф і тривалість часу для однієї особи, якій потрібно допомогти. Усі цілі числа знаходяться в діапазоні від 0 до 10000 включно. Вхід закінчується двома нулями на окремому рядку.
Вихідні дані
Для кожного ув'язненого вихід складається з одного рядка, що містить максимальну кількість осіб, яким можна допомогти в межах заданого часового ліміту. Якщо неможливо допомогти нікому, не перевищуючи ліміт, виведіть "Mission Impossible".