Problem Description

Xiao C wants to buy $n$ items. These items have prerequisite relations and must be bought in order (that is, he can only buy item $i+1$ after buying item $i$).

Initially, he has $m$ coupons and infinitely many coins. Each item has two attributes: price $a_i$ and coupon usage limit $b_i(0\le b_i\le a_i)$.

The process of buying one item is as follows:

• Choose to use $x(0\le x\le b_i)$ coupons, and pay $a_i-x$ coins and $x$ coupons.
• After the purchase, he can get $\lfloor \frac{a_i-x}{c} \rfloor$ coupons (that is, in one purchase, for every $c$ coins paid, he gets one coupon; $c$ is a given constant).

Xiao C wants to find the minimum number of coins needed to buy all items.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$, indicating 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,...,a_n$, representing the prices of the items.
• The third line contains $n$ integers $b_1,b_2,...,b_n$, representing the coupon usage limits.

Output Format

For each test case, output one line:

• Output one integer, representing the minimum number of coins required.

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

34
34
95
463

见附件 ex_shop2.in。

见附件 ex_shop2.out。

Hint

For all testdata, $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: $\texttt{1s}$.

Memory limit: $\texttt{2048MB}$.

Translated by ChatGPT 5