Помощь-или-иначе
В исправительной колонии для финансовых специалистов скоро пройдет ежегодное мероприятие по общественным работам, организованное по определенным правилам, подходящим для колонии. Каждому заключенному назначается набор 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".