Sequential Purchases with Coupon Rewards

Little C wants to purchase n items sequentially; that is, he must purchase item i+1 only after buying item i. He initially possesses m coupons and has an unlimited number of coins. Each item i is characterized by a price a_i and a coupon usage limit b_i (with 0 \le b_i \le a_i). The purchase process for each item is as follows:

1. Choose an integer x (where 0 \le x \le \min(b_i, current\ coupons)), use x coupons and pay a_i - x coins.
2. After the purchase, you receive \(\left\lfloor \frac{a_i - x}{c} \right\rfloor\) new coupons (i.e. for every c coins spent, you earn one coupon).

Your task is to determine the minimum number of coins required to purchase all n items while following the given order. Formally, if you denote the chosen coupon usage for item i by x_i, the total coin cost is \[ \sum_{i=1}^{n} (a_i - x_i), \] subject to the constraints:

• 0 \le x_i \le b_i for every item i,
• The coupons available before purchasing item i (say \text{coupon}_{i}) must satisfy x_i \le \text{coupon}_{i}, and \[ \text{coupon}_{i+1} = \text{coupon}_{i} - x_i + \left\lfloor \frac{a_i - x_i}{c} \right\rfloor, \] with \text{coupon}_1 = m.

inputFormat

The first line contains three integers n, m, and c separated by spaces.

The second line contains n integers: a₁, a₂, \ldots, a_n.

The third line contains n integers: b₁, b₂, \ldots, b_n.

outputFormat

Output a single integer — the minimum number of coins required to purchase all items.

sample

1 0 3
5
2

5