(RankList for this Question)
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.
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.
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.
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.
Log In to solve the Question