5.3 To the Mission

Score: 30pts

Time Limit: 5.00 sec

Pesla has a mission to prepare N cars for their journey into space by charging them. Each car, denoted as the i th car, possesses a specific energy capacity represented by Ai Watt-hours.

To accomplish this task, Pesla has access to M power outlets, each capable of supplying Bj Watt of power. Each outlet can charge one car at a time, and likewise, a car can be charged by only one outlet.

Your challenge is to determine the maximum total energy, in Watt-hours, that can be stored in all the cars after H hours of charging.

Note:

-A power outlet cannot charge a different car even after completely charging a car.

-Energy is the product of power and time. For instance, a car can store 1 Watt-hour of energy if it is charged at a power station with 1 Watt power for 1 hour.

To accomplish this task, Pesla has access to M power outlets, each capable of supplying Bj Watt of power. Each outlet can charge one car at a time, and likewise, a car can be charged by only one outlet.

Your challenge is to determine the maximum total energy, in Watt-hours, that can be stored in all the cars after H hours of charging.

Note:

-A power outlet cannot charge a different car even after completely charging a car.

-Energy is the product of power and time. For instance, a car can store 1 Watt-hour of energy if it is charged at a power station with 1 Watt power for 1 hour.

Constraints

1≤T≤10^5

1≤N,M,H,Ai,Bi≤10^5

The sum of N over all test cases won't exceed 10^5.

The sum of M over all test cases won't exceed 10^5.

1≤N,M,H,Ai,Bi≤10^5

The sum of N over all test cases won't exceed 10^5.

The sum of M over all test cases won't exceed 10^5.

Input Format

-The first line of input will contain a single integer T, the number of test cases.

-The first line of each test case contains 33 space-separated integers N, M, and H, the number of cars, the number of power outlets, and the number of hours respectively.

-The second line of each test case contains N space-separated integers, the energy capacities (in Watt-hour) of the N cars.

-The third line of each test case contains M space-separated integers, the power (in Watt) of the M power outlets.

-The first line of each test case contains 33 space-separated integers N, M, and H, the number of cars, the number of power outlets, and the number of hours respectively.

-The second line of each test case contains N space-separated integers, the energy capacities (in Watt-hour) of the N cars.

-The third line of each test case contains M space-separated integers, the power (in Watt) of the M power outlets.

Output Format

For each test case, print the maximum total energy (in Watt-hours) stored in all cars after H hours.

Example 1

Input:

3

1 2 2

100

20 40

2 1 2

10 20

11

3 2 1

30 30 30

40 20

Output:

80

20

50

Explanation:

Test case 1: We use the second power outlet to charge the car. After 2 hours, 40⋅2=80 watt-hours of energy is stored in the car.

Test case 2: We use the power outlet to charge the second car. After 2 hours, 11⋅2=22 watt-hours of energy is generated but since the car has the capacity of 20, it will store only 20 watt-hours of energy.

Test case 3: We use the first power outlet to charge the first car and second outlet to charge the second car. After 1 hour, the first car will store 30 watt-hours of energy (due to its maximum capacity) and second car will store 20 watt-hours of energy.

Thus, the cars will store a total of 50 watt-hours of energy.

3

1 2 2

100

20 40

2 1 2

10 20

11

3 2 1

30 30 30

40 20

Output:

80

20

50

Explanation:

Test case 1: We use the second power outlet to charge the car. After 2 hours, 40⋅2=80 watt-hours of energy is stored in the car.

Test case 2: We use the power outlet to charge the second car. After 2 hours, 11⋅2=22 watt-hours of energy is generated but since the car has the capacity of 20, it will store only 20 watt-hours of energy.

Test case 3: We use the first power outlet to charge the first car and second outlet to charge the second car. After 1 hour, the first car will store 30 watt-hours of energy (due to its maximum capacity) and second car will store 20 watt-hours of energy.

Thus, the cars will store a total of 50 watt-hours of energy.