[Java, Need Help!]

Deals on Cookies

It is lunch time again, and I am starving. I would like to buy some cookies. from a small cafe, named Cafe CSC201 owned and operated by CSC201.

Cafe CSC often offers discounts for buying multiple cookies. I wonder which of the discounts provides the best values.

For this problem, please write a program to help me find the best deal.

Input

The input contains multiple scenarios. Each scenario starts with a line containing two numbers.

N ( 1 <= N <=10 ) and M ( 1 <= M <20 ), N means there are N deals available, M means the max amount of cookies I want to buy,

(I may buy less if i get the best deal). Following N lines, each line has two numbers; x and y which represent an offer to buy x cookies for $y.

The input will be terminated by a line containing the character 0 0.

Output

For each scenario, print Purchase x cookies for $y for the best offer that matches requirements (the bes deal but less or equal to the number of cookies iwant to buy).

If there are multiple best offers , print the one which buys more tickets (but still be less or equal to the number of cookies i want to buy).

If there is no suitable offer (may require to buy more cookies than i want to).

Sample input data Sample output data

5 6 Purchase 6 cookies for $6

12 10 Purchase 3 cookies for $5

9 8 Purchase 1 cookie for $3

6 6 Purchase 2 cookies for $4

3 3 No good deals

1 2

3 5

1 3

3 5

4 7

3 2

3 5

1 3

4 7

3 2

3 6

1 2

2 4

1 3

4 10

0 0

given

case2.txt

2 5

1 2

6 8

0 0