P9225 "PEOI Rd1" Treasure (treasure)

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.

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 one positive integer in a single line, which is the answer.

#### 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.** |Subtask|Score|Special Constraints| |:-:|:-:|:-:| |$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$|None| 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