Description

YSGH has a number $x$ with initial value $0$. For the next $n$ minutes, each minute YSGH can add an integer $y$ to $x$, where $y \in [-k, k]$. At the same time, YSGH must ensure that at the end of the $i$-th minute, $x \le a_i$.

Let $b_i$ be the value of $x$ at the end of the $i$-th minute. Now YSGH gives you a sequence $w$ of $n$ numbers. You need to maximize $\displaystyle \sum_{i = 1}^{n} b_i w_i$.

You only need to output the maximum value.

Input Format

The first line contains two positive integers $n, k$, with the same meaning as in the statement.

The second line contains $n$ integers, where the $i$-th integer is $a_i$, with the same meaning as in the statement.

The third line contains $n$ integers, where the $i$-th integer is $w_i$, with the same meaning as in the statement.

It is guaranteed that the input ensures there exists at least one sequence $b$ that satisfies the conditions.

Output Format

The first line contains one integer, which is the answer.

5 1
4 3 2 3 2
5 7 -5 9 -10

24

Hint

For $10\%$ of the data, $n \le 10$, $k \le 1$.
For $20\%$ of the data, $n \le 100$.
For $30\%$ of the data, $n \le 10^3$.
For $50\%$ of the data, $n \le 10^4$.
There is another $10\%$ of the data where $w_i \ge 0$.
For $100\%$ of the data, $1 \le n \le 10^6$, $-10^6 \le w_i \le 10^6$, $0 \le a_i \le 10^8$, $1 \le k \le 100$.

Translated by ChatGPT 5