Welcome to ZOJ Contests Information Problems Runs Statistics Ranklist Clarification 152 - The 18th Zhejiang University Programming Contest Sponsored by TuSimple - F
Schrödinger's Knapsack

Time Limit: 1 Second      Memory Limit: 131072 KB

DreamGrid has a magical knapsack with a size capacity of $c$ called the Schrödinger's knapsack (or S-knapsack for short) and two types of magical items called the Schrödinger's items (or S-items for short). There are $n$ S-items of the first type in total, and they all have a value factor of $k_1$; While there are $m$ S-items of the second type in total, and they all have a value factor of $k_2$. The size of an S-item is given and is certain. For the $i$-th S-item of the first type, we denote its size by $s_{1,i}$; For the $i$-th S-item of the second type, we denote its size by $s_{2,i}$.

But the value of an S-item remains uncertain until it is put into the S-knapsack (just like Schrödinger's cat whose state is uncertain until one opens the box). Its value is calculated by two factors: its value factor $k$, and the remaining size capacity $r$ of the S-knapsack just after it is put into the S-knapsack. Knowing these two factors, the value $v$ of an S-item can be calculated by the formula $v = kr$.

For a normal knapsack problem, the order to put items into the knapsack does not matter, but this is not true for our Schrödinger's knapsack problem. Consider an S-knapsack with a size capacity of 5, an S-item with a value factor of 1 and a size of 2, and another S-item with a value factor of 2 and a size of 1. If we put the first S-item into the S-knapsack first and then put the second S-item, the total value of the S-items in the S-knapsack is $1 \times (5-2) + 2 \times (3-1) = 7$; But if we put the second S-item into the S-knapsack first, the total value will be changed to $2 \times (5-1) + 1 \times (4-2) = 10$. The order does matter in this case!

Given the size of DreamGrid's S-knapsack, the value factor of two types of S-items and the size of each S-item, please help DreamGrid determine a proper subset of S-items and a proper order to put these S-items into the S-knapsack, so that the total value of the S-items in the S-knapsack is maximized.

#### Input

The first line of the input contains an integer $T$ (about 500), indicating the number of test cases. For each test case:

The first line contains three integers $k_1$, $k_2$ and $c$ ($1 \le k_1, k_2, c \le 10^7$), indicating the value factor of the first type of S-items, the value factor of the second type of S-items, and the size capacity of the S-knapsack.

The second line contains two integers $n$ and $m$ ($1 \le n, m \le 2000$), indicating the number of the first type of S-items, and the number of the second type of S-items.

The next line contains $n$ integers $s_{1,1}, s_{1,2}, \dots, s_{1,n}$ ($1 \le s_{1,i} \le 10^7$), indicating the size of the S-items of the first type.

The next line contains $m$ integers $s_{2,1}, s_{2,2}, \dots, s_{2,m}$ ($1 \le s_{2,i} \le 10^7$), indicating the size of the S-items of the second type.

It's guaranteed that there are at most 10 test cases with their $\max(n, m)$ larger than 100.

#### Output

For each test case output one line containing one integer, indicating the maximum possible total value of the S-items in the S-knapsack.

#### Sample Input

3
3 2 7
2 3
4 3
1 3 2
1 2 10
3 4
2 1 2
3 2 3 1
1 2 5
1 1
2
1


#### Sample Output

23
45
10


#### Hint

For the first sample test case, you can first choose the 1st S-item of the second type, then choose the 3rd S-item of the second type, and finally choose the 2nd S-item of the first type. The total value is $2 \times (7-1) + 2 \times (6-2) + 3 \times (4-3) = 23$.

For the second sample test case, you can first choose the 4th S-item of the second type, then choose the 2nd S-item of the first type, then choose the 2nd S-item of the second type, then choose the 1st S-item of the second type, and finally choose the 1st S-item of the first type. The total value is $2 \times (10-1) + 1 \times (9-1) + 2 \times (8-2) + 2 \times (6-3) + 1 \times (3-2) = 45$.

The third sample test case is explained in the description.

It's easy to prove that no larger total value can be achieved for the sample test cases.

Submit    Status