The PDF version of this problem can be downloaded here.
You have just traveled to the Pizza Town. As the name implies, the most famous food
in the town is pizza. There are n pizza restaurants, and each sells a unique pizza. You
would like to try all of them, if possible, so you plan to eat the pizzas one-by-one. What
you will do is the following:
1. Go to one pizza store and buy one pizza.
2. Go back to your hostel room and eat that pizza.
3. Go to another pizza store and buy another pizza.
4. ...
Then you nd out that you may quickly get tired. You have e energy now. The
round trip to the i-th restaurant costs you ai energy, and eating the pizza from the i-th
restaurant gives you bi energy. Once you use up all e energy, you will get tired and
cannot do any thing. However, if you arrive home with 0 energy, you can still eat the
pizza that you bring back. How many pizza can you eat before running out of energy?
The first line of the input file contains an integer T (1 ≤ T ≤ 70) indicating the number of test cases.
Each test case starts with a line containing two integers, n and e (1 ≤ n ≤ 105,
0 ≤ e ≤ 108). The next line contains n integers, a1,..., an. Yet the next line also
contains n integers, b1,..., bn (0 ≤ ai, bi ≤ 108).
For each test case output the maximum number of pizzas that you can buy and eat.
2 2 5 3 5 2 2 4 3 2 1 3 1 0 1 2 0
1 3
For the rst test case, you may go to either of the restaurants, but not both. For the
second test case, you can have 2 -> 3 -> 1, 2 -> 3 -> 4, 3 -> 2 -> 1, 3 -> 2 -> 4, or 3 -> 4 -> 2.
Migrated from old NTUJ.
tmt514
| No. | Testdata Range | Score |
|---|