Solar Charging

Interview

Time limit0.5sMemory limit512 MB

Summary

Each day the battery is either charged by sunlight or used, and the task is to find the minimum electricity cost while ending at or above the starting charge.

Level: Medium5 of 10
Topics: Dynamic programming, Implementation
Solved: No attempts yet

Problem

Albert recently bought a battery that is charged by solar power, and he wants to use it to save electricity. The battery cannot be charged and used at the same time. So each morning, he decides once per day whether to charge the battery or use it. Changing the decision more often is too much trouble.

The battery currently holds $B$ units, and its maximum capacity is $C$ . On day $i$ , he plans to use exactly $D_i$ units of electricity. If the battery holds at least $D_i$ on day $i$ , he can use appliances from the battery, and the charge drops by $D_i$ . No household electricity is used that day, so there is no cost. If he charges the battery on day $i$ , the charge rises by $P_i$ , but it cannot exceed $C$ . Since charging and using cannot happen together, he must use household electricity that day and pay for it. The electricity rate changes every day. On day $i$ the rate per unit is $F_i$ , so he pays $D_i \cdot F_i$ that day.

Under these conditions, Albert uses the electricity he needs each day for the next $N$ days. After day $N$ , the battery must hold at least $B$ , the starting charge. Find the minimum total electricity cost.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains $N$ , $B$ , and $C$ , separated by spaces. The second line contains the array $P$ , the amount the battery can be charged by sunlight each day, separated by spaces. The third line contains the array $F$ , the electricity rate that changes each day, separated by spaces. The fourth line contains the array $D$ , the amount of electricity used each day, separated by spaces.

Output

For each test case, print the minimum electricity cost on its own line.

Constraints

$1 \le T \le 10$
$1 \le N, C \le 1000$
$0 \le B \le C$
$1 \le i \le N$ $1 \leq i \leq N$ for each $i$ $i$ :
- $1 \le D_i, P_i \le 1000$
- $1 \le F_i \le 10^9$

Examples1

Example 1

Input

5
4 0 10
10 10 10 1
100 100 100 100
4 3 2 1
4 10 10
10 10 10 1
100 100 100 100
4 3 2 1
4 9 10
10 10 10 9
100 100 100 100
3 3 3 1
5 3 20
3 5 3 5 3
2 10 3 5 8
5 4 3 4 5
5 0 1
1 1 1 1 1
1000000000 1000000000 1000000000 1000000000 1000000000
1000 1000 1000 1000 1000

Expected output

400
300
100
39
5000000000000