Relocation#2534
Emma and Eric are moving to their new house after returning from their honeymoon. Fortunately, they have a few friends helping them relocate. To move the furniture, they have only two compact cars, which complicates things a bit. Since the furniture does not fit inside the cars, Eric wants to put it on top of the cars. However, each car can support only a certain weight on its roof, so they will need to make several trips to move everything. The moving schedule is as follows:
At their old place, they load furniture onto both cars.
They then drive both cars to the new house and carry the furniture inside.
Finally, everyone returns together to the old place. This process repeats until everything is moved to the new house.
Note that the group always stays together so that the move is more fun and nobody feels lonely. Since the distance between the houses is quite large, Eric wants to make as few trips as possible.
Given the weights w_i of each piece of furniture and the capacities C_1 and C_2 of the two cars, how many trips to the new house do they need to make to move all the furniture? If a car has capacity , the sum of the weights of all the furniture it carries on a single trip cannot exceed .
The first line contains the number of scenarios. Each scenario consists of one line with three numbers , C_1, and C_2. C_1 and C_2 are the capacities of the cars (1 \leq C_i \leq 100), and is the number of pieces of furniture (1 \leq n \leq 10). The following line contains integers w_1, w_2, \ldots, w_n, the weights of the furniture (1 \leq w_i \leq 100). It is guaranteed that each piece of furniture can be carried by at least one of the two cars.
For each scenario, start the output with a line containing "Scenario #i:", where is the scenario number starting from . Then print a single line with the number of trips to the new house needed to move all the furniture. End each scenario with a blank line.
Example 1