Maximizing Weighted Cumulative Sum

YSGH has a number $x$, initially $x=0$. Over the course of $n$ minutes, at each minute $i$ (for $1\le i\le n$) YSGH can add an integer $y$ to $x$, where $y \in [-k,k]$. However, after each minute, the updated value $x$ (denoted as $b_i$) must satisfy $b_i \le a_i$.

Given a sequence of $n$ integers $w = [w_1, w_2, \ldots, w_n]$, the goal is to choose the increments so as to maximize the objective [ \sum_{i=1}^{n} b_i \cdot w_i, ] where [ b_i = x_{i-1} + y_i, \quad x_0 = 0, \quad \text{and} \quad x_i \le a_i \text{ for } 1\le i\le n. ]

It can be shown that by rewriting the sum as [ \sum_{i=1}^{n} b_i \cdot w_i = \sum_{j=1}^{n} y_j \left(\sum_{i=j}^{n} w_i\right), ] the decision at minute $j$ should depend on the sign of [ S(j)=\sum_{i=j}^{n} w_i. ] If $S(j) \ge 0$, one should choose the maximum possible increment (subject to the constraint at that minute), and if $S(j) < 0$, one should choose the minimum allowed increment.

You are to compute and output the maximum achievable value of the objective.

inputFormat

The input consists of three lines:

• The first line contains two integers $n$ and $k$, denoting the number of minutes and the maximum absolute increment allowed each minute, respectively.
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the upper bound for $x$ after the $i$th minute.
• The third line contains $n$ integers $w_1, w_2, \ldots, w_n$, representing the weight sequence.

outputFormat

Output a single integer: the maximum possible value of [ \sum_{i=1}^{n} b_i \cdot w_i, ] subject to the conditions described.

sample

3 5
8 10 15
1 2 3

70