Drone Packing

Time limit2sMemory limit512 MB

Summary

Choose items to load onto two drones with separate weight capacities so total value is maximized, with no item split or shared.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

The North Pole delivery centre is retiring the sleigh and moving to drones. The first trial run has only two drones, and each drone has a limit on the weight it can carry.

You are given a list of candidate presents. Every present has a weight and a value, and the value is an integer in thousands of dollars. Choose presents and split them between the two drones so that the total value carried is as large as possible. A present cannot be cut apart, and one present cannot be shared by the two drones. Leaving presents behind is allowed.

The weights loaded onto a drone must sum to at most that drone's limit. Find the largest total value you can achieve.

Input

The input holds several problems. The first line has the number of problems $P$ ( $1 \le P \le 10$ ).

Three lines follow for each problem. The first line has the number of candidate presents $N$ ( $1 \le N \le 100$ ) and the carrying limits of the two drones $W_1$ and $W_2$ ( $1 \le W_1, W_2 \le 1000$ ). The second line has the $N$ weights $w_i$ ( $1 \le w_i \le 100$ ). The third line has the $N$ values $v_i$ ( $1 \le v_i \le 100$ ). Numbers on a line are separated by single spaces, with no leading or trailing spaces.

Output

Print one line for each problem. The line is Problem , the problem number counting from 1, : , and the largest total value the two drones can carry.

If the answer to the first problem is 22, print Problem 1: 22.

Examples6

Example 1

Input

2
4 9 4
3 4 5 6
5 7 9 10
6 9 11
3 4 5 6 3 4
2 3 4 5 3 3

Expected output

Problem 1: 22
Problem 2: 16

Example 2
Input
```
1
1 2 3
5
100
```
Expected output
```
Problem 1: 0
```
Example 3
Input
```
1
1 2 5
5
100
```
Expected output
```
Problem 1: 100
```
Example 4
Input
```
1
2 9 3
5 7
10 13
```
Expected output
```
Problem 1: 13
```
Example 5
Input
```
1
1 1 1
1
1
```
Expected output
```
Problem 1: 1
```

Example 6

Input

Expected output

Problem 1: 10