Given a set of points $pos_{1...n}$ on a number line, there are some wolves located at these points. Their positions are within the range of $pos_{1...n}$. They want to prey on some rabbits, but due to limited energy, each wolf can prey on at most one rabbit. Since they cannot starve, each wolf must prey on at least one rabbit.

There are two main bases for rabbits located at $0$ and $L$, each containing an infinite number of rabbits. Additionally, there are some stray rabbits whose positions are also within the range of $pos_{1...n}$.

A wolf at position $x$ wanting to prey on a rabbit at position $y$ incurs a cost of $|x-y|$. What is the minimum total cost?

Input

The first line contains a positive integer $n$, representing the size of the set of positions where wolves and rabbits exist.

The next line contains $n$ integers $a_i$. If $a_i > 0$, it means there are $a_i$ wolves at position $pos_i$; otherwise, it means there are $-a_i$ rabbits at position $pos_i$.

The next line contains $n+1$ integers $b_{0 \sim n}$, representing $pos_{i+1} - pos_i$, where $pos_0 = 0$ and $pos_{n+1} = L$. Note that $b_i$ may be $0$.

Output

Output a single integer representing the answer.

Examples

Input 1

1
-100
1 1

Output 1

0

Input 2

1
100
1 1

Output 2

100

Note 3~4

See the additional files.

Constraints

For $100\%$ of the data, let $c_i = |a_i|$. Then $1 \le n \le 5 \times 10^5$, $0 \le c_i \le 10^5$, and $0 \le L \le 5 \times 10^8$.

The additional constraints for each subtask are as follows: