Relocation

Interview

Time limit1sMemory limit128 MB

Summary

Split up to 10 furniture items between two cars with capacity limits so that every item gets moved in the fewest number of paired trips.

Level: Medium5 of 10
Topics: Dynamic programming, Binary search, Brute force, Backtracking
Solved: No attempts yet

Problem

Emma and Eric are moving into the new house they bought after returning from their honeymoon. Luckily, a few friends are helping with the move. To carry the furniture they only have two small cars, which makes things a little complicated. The furniture does not fit inside the cars, so Eric wants to put it on the roofs instead. However, each car's roof can bear only a limited weight, so several trips will be needed to move everything.

The move works like this:

At the old house, they load furniture onto the two cars.
They drive both cars to the new house and carry the furniture upstairs.
Everyone returns to the old house, and the process repeats until all the furniture has been moved.

The whole group always travels together so the move stays fun and nobody is left alone. Because the two houses are far apart, Eric wants to make as few trips as possible.

Given the weight $w_i$ of each piece of furniture and the roof capacities $C_1$ and $C_2$ of the two cars, how many trips to the new house are required to move all the furniture? A car with capacity $C$ may carry furniture whose total weight is at most $C$ on any single trip.

Input

The first line contains the number of scenarios. Each scenario is given on two lines. The first line contains three integers $n$ , $C_1$ , and $C_2$ : the number of pieces of furniture $n$ ( $1 \le n \le 10$ ) and the roof capacities $C_1$ and $C_2$ ( $1 \le C_i \le 100$ ). The second line contains $n$ integers $w_1, \dots, w_n$ , the weights of the furniture ( $1 \le w_i \le 100$ ). Every piece of furniture can be carried by at least one of the two cars.

Output

For each scenario, first print a line Scenario #i:, where $i$ is the scenario number starting from 1. On the next line, print the minimum number of trips to the new house needed to move all the furniture. Separate consecutive scenarios with a blank line.

Examples2

Example 1

Input

2
6 12 13
3 9 13 3 10 11
7 1 100
1 2 33 50 50 67 98

Expected output

Scenario #1:
2

Scenario #2:
3

Example 2
Input
```
1
3 10 10
10 10 10
```
Expected output
```
Scenario #1:
2
```