Problem Description

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.

Input Format

The input consists of three lines in the following format.

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 Format

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

3
10 6 10
5 2 4

18

1
4
10

4

5
100 100 100 100 100
5 1 4 2 3

35

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

118

Hint

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.