Traditional Game

Many years ago, when Chmyaaax was not yet evil, he loved to play a traditional game from the tribes of the Link-Cut planet system with Anton. The game takes place on a $1\times n$ board, where each cell contains a pair of numbers $a_i,b_i$,all numbers are distinct. There is also a game piece that initially is at position $1$, and a magical balance that initially equals $0$. The players take turns making moves, with Chmyaaax going first.

Suppose the game piece is currently on cell $i$.

1. On his turn, Chmyaax can move the piece forward by $k$ cells, where $k>0$, subtracting $k\cdot a_i$ coins from the balance, and changing the position of the piece to $i+k$.

2. On his turn, Anton can move the piece backward by $k$ cells, where $k>0$, adding $k\cdot b_i$ coins to the balance, and changing the position of the piece to $i-k$, or he can use magic to move the piece to the last cell, adding $(n-i)\cdot b_i$ coins to the balance, and setting the piece to position $n$.

At any point in time, the piece cannot go off the board (i.e.,its position must be greater than $0$ and less than $n+1$). The game ends when the piece reaches cell $n$. Chmyaaax's goal is to maximize the balance, while Anton's goal is to minimize it. If both players play optimally, what will the balance be at the end of the game? It can be shown that under these conditions, the game will not continue infinitely.

Input

The first line contains one integer $n(2\le n\le 10^6)$ — the size of the board on which the game happens.

The second line contains $n$ integers $a_i(-10^9\le a_i\le 10^9)$.

The third line contains $n$ integers $b_i(-10^9\le b_i\le 10^9)$.

For each pair of $i$ and $j$, such that $i\ne j$ and $1\le i,j\le n$ it holds $a_i\ne a_j$, $b_i\ne b_j$ and $a_i\ne b_j$.

Output

You need to output that value of balance at the end of the game, if both players play optimally.

Examples

Note

In the first test sample, for Chmyaax is optimal to jump from the start to the end decreasing the balance by $33\cdot 7=231$, achieving the balance $-231$. It could be proven that there isn't any strategy for him, with which he can achieve bigger balance.

In the second test sample, Chmyaax can jump to the cell $2$ changing balance to $-5\cdot 2=-10$, Anton can move the piece to the last cell, adding to the balance $15\cdot 2=30$ making balance equal $20$.

Scoring

1. ($25$ points): $n\le 20$;

2. ($30$ points): $n\le 50$, $-200\le a_i,b_i\le 200$;

3. ($40$ points): $n\le 5000$;

4. ($30$ points): $n\le 10^5$;

5. ($75$ points): no additional constraints.