Xiao C wants to purchase $n$ items. These items have a precedence relationship and must be purchased sequentially (i.e., the $i$-th item must be purchased before the $(i+1)$-th item).

He initially has $m$ coupons and an infinite supply of gold coins. Each item has two attributes: a price $a_i$ and a maximum coupon usage limit $b_i$ ($0 \le b_i \le a_i$).

The process of purchasing an item is as follows:

• Choose to use $x$ ($0 \le x \le b_i$) coupons, paying $a_i - x$ gold coins and $x$ coupons.
• After the purchase, you receive $\lfloor \frac{a_i - x}{c} \rfloor$ coupons (i.e., in a single purchase, for every $c$ gold coins paid, you receive one coupon, where $c$ is a given constant).

Xiao C wants to find the minimum number of gold coins required to purchase all items.

Input

This problem contains multiple test cases. The first line contains an integer $T$, representing the number of test cases.

For each test case:

• The first line contains three integers $n, m, c$.
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$ representing the price of each item.
• The third line contains $n$ integers $b_1, b_2, \dots, b_n$ representing the maximum coupon usage limit for each item.

Output

For each test case, output one line:

• Output a single integer representing the minimum number of gold coins required.

Examples

Input 1

4
6 16 2
17 14 13 5 13 4
12 5 5 2 10 2
6 4 2
8 1 20 10 4 10
8 1 15 3 4 6
5 40 7
21 47 7 25 47 
9 26 4 4 39 
5 151 10
86 84 164 158 160
43 42 82 79 80

Output 1

34
34
95
463

Input 2

See the provided file.

Subtasks

For all data, $1 \le \sum n \le 10^6, 1 \le m, a_i, b_i \le 10^9, 2 \le c \le 10^9$.

Subtask 1 (5 pts): $1 \le T \le 5, 1 \le n \le 10, 1 \le m, \sum a_i, \sum b_i \le 10$

Subtask 2 (10 pts): $a_i = b_i$

Subtask 3 (10 pts): $1 \le \sum n \le 500, 1 \le \sum m, \sum a_i, \sum b_i \le 500$

Subtask 4 (10 pts): $1 \le \sum n \le 6000, 1 \le \sum m, \sum a_i, \sum b_i \le 6000$

Subtask 5 (10 pts): $1 \le \sum n \le 6000$

Subtask 6 (15 pts): $1 \le \sum n \le 2 \times 10^5, 2 \le c \le 20$

Subtask 7 (10 pts): $1 \le \sum n \le 1 \times 10^6, 2 \le c \le 20$

Subtask 8 (15 pts): $1 \le \sum n \le 2 \times 10^5$

Subtask 9 (15 pts): $1 \le \sum n \le 1 \times 10^6$