Help-or-else

A correctional facility is about to hold its yearly community-service event under some strict rules. Each participant is assigned a set $P$ of $N$ people whose finances they may help with, together with a time budget of $K$ minutes.

For the $j$-th person ($1 \le j \le N$) two integers are known: a penalty $e_j$ that is charged if the participant chooses not to advise that person, and a duration $d_j$ (in minutes) required to advise that person.

The participant starts at time $T = 0$. If they begin working with the $j$-th person at time $T$, they must finish no later than $T + d_j$; a value $C_j = T + d_j$ is charged, and they may not start working with anyone else before time $T + d_j$ (people are helped one at a time, back to back).

Let $S$ be the set of people who are actually helped. The total number of minutes used is

$\sum_{x \in S} C_x + \sum_{x \in P \setminus S} e_x.$

Write a program that computes the maximum number of people a participant can help without the total used minutes exceeding the limit $K$.

The input contains the data for several participants. Each participant's description begins with a line holding two integers $N$ and $K$, separated by a single space: the number of people and the time budget, with $0 < N \le 200$ and $0 < K \le 6000$. Each of the following $N$ lines contains two integers separated by a single space — the penalty and the duration of one person to be assisted — with every integer between $0$ and $10000$ inclusive. The input terminates with a line containing two zeros.

For each participant, print a single line in the form i: X, where i is the participant's index counted from $1$ in the order the participants appear, and X is the maximum number of people that can be helped without exceeding the $K$-minute limit. If it is impossible to keep the total used minutes within $K$, print i: Mission Impossible instead.