Problem Description

One day, wrzSama was treasure hunting, and suddenly fell into a magical room. There are $n$ machines in this room. Machine $i$ can produce $2^i$ diamonds.

More specifically, wrzSama can spend $a_i$ time to start machine $i$, and it will produce $2^i$ diamonds. These machines have a very special property: every time he uses machine $i$, its start-up time $a_i$ increases by $b_i$. This means that when he wants to get these $2^i$ diamonds for the second time, it will take $a_i + b_i$ time. The time keeps increasing in this way, and the $x$-th start will take $a_i + (x - 1) b_i$ time.

wrzSama needs to obtain at least $2^n$ diamonds to get the treasure. Please find the minimum total time required.

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

Output one positive integer in a single line, which is the answer.

3
1 2 3
3 2 1

3

3
1 2 100
1 2 1

5

4
1 2 100 100
1 2 1 1

15

Hint

Sample Explanation

Sample 1: directly obtain $2^3$, costing time 3.

Sample 2: obtain 2 copies of $2^1$, costing time 3, then spend time 2 to obtain one $2^2$. In this way, wrzSama can get $2 \times 2^1 + 2^2 = 8 = 2^n$.

Sample 3: obtain 2 copies of $2^1$ and 3 copies of $2^2$.

Constraints

This problem uses bundled tests.

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

Translated by ChatGPT 5