题目描述

有一天 wrzSama 在寻宝，突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器，第 $i$ 个机器可以生产 $2^i$ 个钻石。

具体地，wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器，让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质，每当他用一次第 $i$ 个机器后，会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻石时就需要 $a_i + b_i$ 的时间，每次不断累加，第 $x$ 次开动就需要 $a_i+(x-1)b_i$ 的时间。

wrzSama 需要得到至少 $2^n$ 个钻石来得到宝藏，请问他最少需要多长时间。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数，表示 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个正整数，表示 $b_1,b_2,\dots,b_n$。

输出格式

一行一个正整数，即为答案。

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

提示

样例解释

样例 1 解释：直接获得 $2^3$，花费 3 的时间。

样例 2 解释：获得 2 个 $2^1$，花费 3 的时间，然后再花 2 的时间获得一个 $2^2$，这样 wrzSama 就可以得到 $2 \times 2^1 + 2^2 = 8 = 2^n$ 了。

样例 3 解释：获得 2 个 $2^1$ 和 3 个 $2^2$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^3$，$1 \le a_i,b_i \le 10^7$。