Problem Description

A data center needs to complete a series of computing tasks in the next $n$ time periods, so it must plan an electricity purchasing strategy in advance to reduce the total cost as much as possible.

Specifically, the $i$-th time period requires $w_i$ units of electricity, and all of this electricity must be ready before the end of the $i$-th time period. You may purchase electricity in any time period: if you buy electricity in the $i$-th time period, then the price is $c_i$ yuan per unit.

However, electricity prices may differ a lot between time periods. To make better use of this, the data center is equipped with an energy storage battery with capacity $k$. With this battery, you can buy more electricity during cheaper periods and store it, then use it later during more expensive periods or when electricity is needed, thus reducing the overall spending.

The battery starts with $0$ units of electricity, and losses during charging and discharging can be ignored. Also, at any time, the amount of electricity in the battery cannot exceed the capacity $k$ and cannot be below $0$.

Now, please compute the minimum amount of money (in yuan) that must be spent to purchase electricity, while ensuring that the electricity demand of every time period can be satisfied.

Input Format

The input consists of 3 lines.

The first line contains two integers $n$ and $k$, representing the number of time periods and the capacity of the energy storage battery.

The second line contains $n$ non-negative integers $w_1, w_2, \dots, w_n$, where $w_i$ denotes the electricity required in the $i$-th time period.

The third line contains $n$ non-negative integers $c_1, c_2, \dots, c_n$, where $c_i$ denotes the price per unit of electricity when purchasing in the $i$-th time period.

Output Format

Output one line with one non-negative integer, representing the minimum electricity purchase cost required to meet the demand of all time periods.

3 1
1 2 1
20 25 100

90

Hint

Sample Explanation

The optimal plan is as follows:

• In the $1$-st time period, buy $2$ units of electricity, costing $2 \times 20 = 40$ yuan; use $1$ unit immediately, and store the other $1$ unit in the battery.
• In the $2$-nd time period, buy $2$ units of electricity, costing $2 \times 25 = 50$ yuan; all $2$ units are used to meet the demand of the current time period.
• In the $3$-rd time period, directly use the remaining $1$ unit of electricity in the battery, with no additional purchase.

Therefore, the total cost is $40 + 50 = 90$ yuan.

Constraints

For $20\%$ of the testdata, $n \leq 10$, $k \leq 10$.

For $40\%$ of the testdata, $n \leq 500$, $k \leq 1000$.

For another $20\%$ of the testdata, $n \leq 3000$, and $\sum w_i \leq 10^6$.

For another $10\%$ of the testdata, $k \leq 100$.

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $0 \leq k \leq 10^9$, $0 \leq w_i, c_i \leq 10^9$.

Translated by ChatGPT 5