B. Two Way Homework
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$A$$$ and $$$B$$$ of length $$$N$$$. For each position $$$i$$$, we need to choose one element either $$$A_i$$$ or $$$B_i$$$ and the goal is to choose values in such a way that the sum of the values is as small as possible. Note that we choose elements in increasing order of $$$i$$$.

However, there is a catch as the problem would be way too easy otherwise. Every time we take a value from array $$$A$$$, the cost of every subsequent value we choose will double.

For example, if we have the arrays:

$$$[4, 1, 3, 4]$$$ $$$[7, 2, 1, 3]$$$

If we choose $$$4$$$ from the first array, this means that for the next $$$3$$$ positions, the true costs will be $$$(2, 6, 8)$$$ and $$$(4, 2, 6)$$$ respectively which can be further doubled as well.

Note that if we take an element from $$$B$$$ this doubling process does not happen.

Input

The first line of the input will contain $$$N$$$, the length of the arrays ($$$1 \leq N \leq 10^5$$$).

The second line of the input will contain the array $$$A$$$ ($$$1 \leq A_i \leq 2 \cdot 10^9$$$).

The third line of the input will contain the array $$$B$$$ ($$$1 \leq B_i \leq 2 \cdot 10^9$$$).

Output

You have to print the minimum sum of the values we can obtain according to the rules of the problem.

Example
Input
2
1 3
4 1
Output
3