E. Elevate To Dominate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

With two Spear of Shojin and a Guinsoo's Rageblade, Pyke is dominating in the arena of Teamfight Tactics.

After bitterly lose to the team based on Glacial and Archers of Lowie's, B21 spent days and nights to research on the mystery of the champion Pyke. He found something interesting, (it might be a bug) but still can bring him great advantages in TFT games.

B21 found $$$N$$$ sets of attacks for Pyke. Each set consists of $$$A_i$$$ attacks. After completing set of attacks of index $$$i$$$, the attack speed of Pyke equals to minimum value between current attack speed and $$$B_i$$$ milliseconds for each attack. And to defeat Lowie, Pyke have to complete all $$$N$$$ sets of attacks. Help B21 find the minimum time Pyke complete all $$$N$$$ sets in milliseconds. Know that, at first Pyke have completed the first set of attacks.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$).

The second line contains $$$N$$$ intergers $$$A_i$$$ ($$$1 \le A_i \le 10^6$$$).

The third line contains $$$N$$$ intergers $$$B_i$$$ ($$$1 \le B_i \le 10^6$$$).

It is guaranteed that $$$A_1 = 1$$$ and $$$B_n = 0$$$ and $$$A_1 \lt A_2 \lt ... \lt A_n$$$ and $$$B_1 \gt B_2 \gt ... \gt B_n$$$.

Output

Print exactly one integer - the minimum time Pyke complete all $$$N$$$ sets in milliseconds.

Examples
Input
5
1 2 3 4 6
5 4 3 1 0
Output
26
Input
6
1 2 3 8 9 10
5 4 3 2 1 0
Output
45
Note

In the first example, Pyke complete set of attacks of index $$$1, 4, 5, 2, 3$$$ respectively or index $$$1, 4, 5, 3, 2$$$.

In the second example, Pyke complete set of attacks of index $$$1, 3, 6, 2, 4, 5$$$ respectively or index $$$1, 3, 6, 2, 5, 4$$$, ......