1335 - Gaewah's Table
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 91
Solved: 14
- Description
- Everyone has a table. So does Geawah. But Gaewah's table is larger than others.
Every table has some Beiju on it. But since Gaewah's table is larger, he may have more Beiju. So he decided to buy boxes with his RP to cover his table, so that there's no space for any Beiju.
The store has n different boxes, each covering some parts of the table and costing some RP. Gaewah's table has e parts, and he has only m units of RP. As is known to all, Gaewah is so good at programming that this problem is absolutely a piece of cake for him. But as he's busy preparing for the contest, he turns to you for help. Please tell him if he can exactly cover the table with no more than m units of RP. And if he can, tell him how many boxes he should take and the minimum units of RP needed. - Input
- Multiple cases, precess to the end of file.
The first line of each case has three numbers, n, m, e.
(0 < m <= 1000000, 0 < n, e <= 1000)
The following n lines each contains two numbers, v[i] and w[i], representing if you want to take the ith box you need to consume v[i] units of RP and you can cover w[i] parts of your table.
(0 < v[i], w[i] <= 1000) - Output
- For each test case, first print the number of case. Cases are numbered 1, 2, 3, ...
If Gaewah can exactly cover his table within the RP limit, and he uses r units of RP, prints "Gaewah can cover his table with only r units of RP.".
If Gaewah can exactly cover his table using more than m units of RP, prints "Gaewah needs more RP..".
Else prints "Impossible".
You can see the sample output for details and clarification. - sample input
-
4 10 8 2 3 4 5 1 6 3 2 2 3 100 20 60 30 40 2 100 3 40 10 60 20
- sample output
-
Case 1: Gaewah can cover his table with only 4 units of RP. Case 2: Gaewah needs more RP.. Case 3: Impossible!
- hint
- source
- Song Xie