P9225 「PEOI Rd1」寻宝（treasure）

有一天 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$ 个钻石来得到宝藏，请问他最少需要多长时间。

无

无

#### 样例解释 样例 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$。 --- #### 数据范围 **本题采用捆绑测试。** |子任务|分值|特殊限制| |:-:|:-:|:-:| |$1$|$16$|$1 \leq n \leq 10$| |$2$|$16$|$1 \leq n \leq 20$| |$3$|$24$|$1 \leq a_i \leq 3 \times 10^3$| |$4$|$44$|无| 对于 $100\%$ 的数据，保证 $1 \le n \le 10^3$，$1 \le a_i,b_i \le 10^7$。