Limits 1s, 512 MB

Mr. X is going to plan a game for the upcoming picnic for his company. Here are the rules,
Every team has n members.

1. You will give a balloon to the first member of your team who you want to go first.
2. After the start of the game, that member will blow the balloon.
3. There will be a bucket at distance d from the starting point.
4. After blowing the balloon, he will run and put the balloon in that bucket and pick a new balloon.
5. Come back to the starting point and give that balloon to another member or keep himself and repeat from 3.
6. A team will disqualify if there is any member who didn’t perform this task and another member performs this task more than 1 time.

Now Mr. X knows who are in his team, and he also collects the data which member takes how many seconds (a) to blow the balloon and also how many seconds (b) that member will take to go from the starting point to the bucket. Now Mr. X wants to know the maximum number of balloons they can put into that bucket within s seconds.

Input

At first, there will be an integer T (1<=T<=10), which is the number of test cases.
The first line of each test case contains three integers n, d and s, separated by spaces. Then there will be n lines each containing 2 integers a and b represent each team members seconds needs to blow the balloon and seconds needs to go from starting point to bucket point.
1 ≤ n, d, s, a, b ≤ 100000

Output

For each test case, print “Case #c: #m” without quote where #c represent the case number and #m represents the maximum number of balloons can be put by Mx. X’s team.

Sample

InputOutput
1
2 1 6
1 1
1 1
Case 1: 2

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.