P10001 [CTT Mutual Test 2023] Discount Shopping

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.

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.

For each test case, output one line: - Output one integer, representing the minimum number of coins required.

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