Traditional Game#11730
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 , and a magical balance that initially equals . The players take turns making moves, with Chmyaaax going first.
Suppose the game piece is currently on cell .
On his turn, Chmyaaax can move the piece forward by cells, where k > 0, subtracting k \cdot a_i coins from the balance, and changing the position of the piece to i + k.
On his turn, Anton can move the piece backward by 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 .
At any point in time, the piece cannot go off the board (i.e., its position must be greater than and less than n + 1). The game ends when the piece reaches cell . 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.
The first line contains one integer (2 \le n \le 10^6) — the size of the board on which the game happens.
The second line contains integers a_i (-10^9 \le a_i \le 10^9).
The third line contains integers b_i (-10^9 \le b_i \le 10^9).
For each pair of and , such that i \neq j and 1 \le i, j \le n it holds a_i \neq a_j, b_i \neq b_j, a_i \neq b_j and for every (1 \le i \le n), a_i \neq b_i.
You need to output the value of the balance at the end of the game, if both players play optimally.
Example
34
7 2 3 4 5 6 9 8 10 1 19 12 13 14 15 16 17 18 11 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
7 2 3 4 5 6 9 8 10 1 19 12 13 14 15 16 17 18 11 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34-231Example
3
2 10 3
15 3 720Example
Example 1
Example 2
In the first test sample, for Chmyaaax it is optimal to jump from the start to the end, decreasing the balance by 33 \cdot 7 = 231, achieving the balance . It could be proven that there isn't any strategy for him, with which he can achieve a bigger balance.
In the second test sample, Chmyaaax can jump to the cell changing the balance to -5 \cdot 2 = -10, Anton can move the piece to the last cell, adding to the balance 15 \cdot 2 = 30 making the balance equal .
( points): n \le 20;
( points): n \le 50, -200 \le a_i, b_i \le 200;
( points): n \le 5000;
( points): n \le 10^5;
( points): no additional constraints.