Minimum Cost for Machine Factory Order Fulfillment

Little T has opened a machine factory. Over N weeks, the cost of raw materials and labor fluctuates. In the i-th week, producing one machine costs $C_i$ yuan. If a machine is not sold immediately, there is a weekly maintenance cost of $S$ yuan per machine, which remains constant.

The factory receives an order to deliver $Y_i$ machines in week i. Machines produced in week i, or stored from previous weeks, can be used to fulfill the order.

Your task is to calculate the minimum total cost to complete all orders over the N weeks.

Hint: A machine produced in week j and used in week i (where j ≤ i) will incur an effective cost of:

$$ cost = C_j + S \times (i - j) $$

You need to choose the optimal production week for each machine ordered, so that the sum of production and storage costs is minimized.

inputFormat

The input is given as follows:

• The first line contains two integers n and S, where n (1 ≤ n ≤ 10⁵) is the number of weeks and S is the storage cost per product per week.
• The second line contains n integers, representing the production cost for each week: $C_1, C_2, ..., C_n$.
• The third line contains n integers, representing the order quantity for each week: $Y_1, Y_2, ..., Y_n$.

You may assume that all integers are non-negative and fit into 32-bit signed integers.

outputFormat

Output a single integer: the minimum total cost to complete the orders over the n weeks.

sample

3 1
3 2 4
1 2 3

16