{"problem":{"name":"「PEOI Rd1」寻宝（treasure）","description":{"content":"有一天 wrzSama 在寻宝，突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器，第 $i$ 个机器可以生产 $2^i$ 个钻石。 具体地，wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器，让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质，每当他用一次第 $i$ 个机器后，会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9225"},"statements":[{"statement_type":"Markdown","content":"有一天 wrzSama 在寻宝，突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器，第 $i$ 个机器可以生产 $2^i$ 个钻石。\n\n具体地，wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器，让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质，每当他用一次第 $i$ 个机器后，会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻石时就需要 $a_i + b_i$ 的时间，每次不断累加，第 $x$ 次开动就需要 $a_i+(x-1)b_i$ 的时间。\n\nwrzSama 需要得到至少 $2^n$ 个钻石来得到宝藏，请问他最少需要多长时间。\n\n## Input\n\n第一行一个正整数 $n$。\n\n第二行 $n$ 个正整数，表示 $a_1,a_2,\\dots,a_n$。\n\n第三行 $n$ 个正整数，表示 $b_1,b_2,\\dots,b_n$。\n\n## Output\n\n一行一个正整数，即为答案。\n\n[samples]\n\n## Note\n\n#### 样例解释\n\n样例 1 解释：直接获得 $2^3$，花费 3 的时间。\n\n样例 2 解释：获得 2 个 $2^1$，花费 3 的时间，然后再花 2 的时间获得一个 $2^2$，这样 wrzSama 就可以得到 $2 \\times 2^1 + 2^2 = 8 = 2^n$ 了。\n\n样例 3 解释：获得 2 个 $2^1$ 和 3 个 $2^2$。\n\n---\n#### 数据范围\n\n**本题采用捆绑测试。**\n\n|子任务|分值|特殊限制|\n|:-:|:-:|:-:|\n|$1$|$16$|$1 \\leq n \\leq 10$|\n|$2$|$16$|$1 \\leq n \\leq 20$|\n|$3$|$24$|$1 \\leq a_i \\leq 3 \\times 10^3$|\n|$4$|$44$|无|\n\n对于 $100\\%$ 的数据，保证 $1 \\le n \\le 10^3$，$1 \\le a_i,b_i \\le 10^7$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9225","tags":["动态规划 DP","O2优化","斜率优化"],"sample_group":[["3\n1 2 3\n3 2 1","3"],["3\n1 2 100\n1 2 1","5"],["4\n1 2 100 100\n1 2 1 1","15"]],"created_at":"2026-03-03 11:09:25"}}