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, \dots, 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, \dots, 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

The input consists of three lines in the following format.

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \end{aligned} $$

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, \dots, 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, \dots, B_N$, each between $1$ and $10^8$, inclusive, representing the complexities of the $N$ tasks.

Output

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

Example

Input 1

3
10 6 10
5 2 4

Output 1

18

Input 2

1
4
10

Output 2

4

Input 3

5
100 100 100 100 100
5 1 4 2 3

Output 3

35

Input 4

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

Output 4

118

Note

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.