Problem Description

One day, wrzSama was on a treasure hunt when he suddenly fell into a magical room. This room contains $n$ machines, where the $i$-th machine can produce $2^i$ diamonds.

Specifically, wrzSama can activate the $i$-th machine for $a_i$ time to produce $2^i$ diamonds. These machines have a special property: each time he uses the $i$-th machine, the activation time $a_i$ increases by $b_i$. This means that for the second time, he needs $a_i + b_i$ time, and it keeps accumulating, so for the $x$-th activation, he needs $a_i + (x-1)b_i$ time.

wrzSama needs to collect at least $2^n$ diamonds to obtain the treasure. What is the minimum amount of time he needs?

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, representing $a_1, a_2, \dots, a_n$.

The third line contains $n$ positive integers, representing $b_1, b_2, \dots, b_n$.

Output Format

A single line containing a positive integer, which is the answer.

Sample Input and Output

Sample Input #1

3
1 2 3
3 2 1

Sample Output #1

3

Sample Input #2

3
1 2 100
1 2 1

Sample Output #2

5

Sample Input #3

4
1 2 100 100
1 2 1 1

Sample Output #3

15

Notes

Sample Explanation

Sample 1 Explanation: Directly obtain $2^3$ with a cost of 3 time units.

Sample 2 Explanation: Obtain 2 units of $2^1$, costing 3 time units, then spend 2 more time units to obtain one $2^2$. This way, wrzSama can get $2 \times 2^1 + 2^2 = 8 = 2^n$.

Sample 3 Explanation: Obtain 2 units of $2^1$ and 3 units of $2^2$.

Data Range

This problem uses subtask testing.

For $100\%$ of the data, it is guaranteed that $1 \le n \le 10^3$ and $1 \le a_i, b_i \le 10^7$.

见题面 Input 部分

见题面 Output 部分