Problem Description

Little C wants to buy \( n \) items, which have prerequisite relationships and must be purchased in sequence (i.e., the \( i+1 \)-th item can only be purchased after the \( i \)-th item).

He initially has \( m \) coupons and an unlimited number of gold coins. Each item has two attributes: the price \( a_i \) and the upper limit for coupon usage \( b_i \) (where \( 0 \le b_i \le a_i \)).

The process of purchasing an item is as follows:

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

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

Input Format

This problem contains multiple sets of data. The first line contains an integer \( T \), indicating the number of data sets.

For each set of data:

• The first line contains three integers \( n \), \( m \), and \( c \).
• The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \), representing the prices of each item.
• The third line contains \( n \) integers \( b_1, b_2, \ldots, b_n \), representing the upper limits for coupon usage for each item.

Output Format

For each set of data, output one line:

• The first line contains an integer, representing the minimum number of gold coins required.

Sample Input and Output

Sample 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

Sample Output #1

34
34
95
463

Sample Input #2

See attached file ex_shop2.in.

Sample Output #2

See attached file ex_shop2.out.

Notes/Hints

For all data, \( 1 \le \sum n \le 10^6 \), \( 0 \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 \)

Time Limit: 1s

Memory Limit: 2048MB

见题面 Input 部分

见题面 Output 部分