eolymp
bolt
Try our new interface for solving problems
Məsələlər

Help-or-else

Help-or-else

\includegraphics{https://static.e-olymp.com/content/dc/dc7de7901b336d116f896e191f72808752a945bd.jpg} A penal colony for finance professionals will soon be holding its annual community service activity with some rules that are considered suitable for a penal colony. Every inmate is assigned a set \textbf{P} of \textbf{N} people to help with their finances and a limit of \textbf{K} minutes. In addition to the circumstances of the jth person, \textbf{1} ≤ \textbf{j} ≤ \textbf{N}, a time penalty of ej for choosing not to give advice and the time duration of \textbf{d_j} minutes allotted to provide the advice are also made clear to the inmate. An inmate starts his community service at time \textbf{T} equal to zero. If the inmate started working with the jth person at time \textbf{T}, then he must terminate his work no later than \textbf{T+d_j}. Regardless of the validity of the advice and time of completion, a value of \textbf{C_j ( = T+ d_j )} is deducted from the inmate's alloted minutes. Also the inmate is not permitted to work with another person until the time \textbf{T+d_j}. If \textbf{S} is the set of people helped by an inmate, then the total number of used minutes is calculated as . Your task is to write a program to calculate the maximum number of persons that can be helped by an inmate without exceeding his K minutes limit. \InputFile Input consists of sets for many inmates. The description for each inmate begins with two integers \textbf{N} and \textbf{K}, separated by a single space on a line by themselves, that represent the number of people and the maximum allowed minutes. \textbf{0}< \textbf{N} ≤ \textbf{200} and \textbf{0} < \textbf{K} ≤ \textbf{6000}. Each of the following N lines contains two integers, separated by a single space, which represent the penalty and time duration one person to be assisted. All integers have values between \textbf{0} and \textbf{10000}, inclusive. Input terminates with two zeros on a line by themselves. \OutputFile For each inmate, the output consists of a single line that contains the maximum number of persons to be helped within the given time limit using the format shown. "\textbf{Mission Impossible}" is entered where not exceeding the given time limit is not possible.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
1 1000
100 1000
2 100
1000 1000
20 10
1 1
0 10000
4 293
61 30
295 39
206 27
94 85
0 0
Çıxış verilənləri #1
1: 1
2: Mission Impossible
3: 0
4: 3
Mənbə The 2011 South Pacific Programming Contest