P17546 [JAG 2026 Summer Camp #2] Vibe Coding

Shobon has decided to use a generative AI to help develop a software project. The project consists of $N$ tasks. Each task $i$ ($i=1,2,\ldots,N$) has a predetermined **implementation workload** $A_i$ and **complexity** $B_i$. Shobon can proceed with these tasks in any order. However, he cannot work on more than one task at the same time. Each task $i$ ($i=1,2,\ldots,N$) can be completed in one of the following two ways: - **Implement the task manually.** Shobon writes the code himself, which takes $A_i$ units of time. - **Use the generative AI.** To make the AI generate correct code, Shobon explains the current task and all previously completed tasks to the AI. Let $S$ be the sum of the complexities of all previously completed tasks. Preparing this explanation takes $S+B_i$ units of time. The AI then finishes the implementation instantly, so no additional implementation time is required. Thus, completing this task by using the AI takes a total of $S+B_i$ units of time. Regardless of which method is used, once task $i$ is completed, its complexity $B_i$ is included in future values of $S$ when using the generative AI. Find the minimum total time required to complete all tasks.

The input consists of three lines in the following format. ```text N A_1 A_2 ... A_N B_1 B_2 ... B_N ``` In the first line, the number of tasks, $N$, is given ($1\le N\le 2\times 10^5$). The second line contains $N$ integers, $A_1,A_2,\ldots,A_N$, each between $1$ and $10^9$, inclusive, representing the implementation workloads of the $N$ tasks. The third line contains $N$ integers, $B_1,B_2,\ldots,B_N$, each between $1$ and $10^8$, inclusive, representing the complexities of the $N$ tasks.

Output in a line the minimum total time required to complete all tasks.

For Sample Input 1, consider using the generative AI for tasks $2$ and $3$ in this order, and then implementing task $1$ manually. - When task $2$ is started, no task has been completed yet. This task takes $0+B_2=2$ units of time. - When task $3$ is started, task $2$ has been completed. This task takes $B_2+B_3=2+4=6$ units of time. - Finally, implementing task $1$ manually takes $A_1=10$ units of time. Thus, all tasks can be completed in $2+6+10=18$ units of time, which is the minimum possible.