Problem Description

There is a juice machine that can make one cup of juice per minute, with any volume.

There are $n$ people standing in a line. The $i$-th person will arrive at the juice machine at minute $t_i$, and take away the cup with the largest volume among all cups that have already been made. The $i$-th person will be satisfied if they get a cup whose volume is greater than or equal to $a_i$. If there is no juice at that time, the $i$-th person will also be unsatisfied.

Ask whether it is possible to make everyone satisfied. If yes, output the minimum possible sum of the volumes of juice needed to satisfy everyone.

Input Format

The first line contains an integer $n$ $(1\leq n\leq 2 \times 10^5)$, representing the number of people in the line.

The next line contains $n$ integers $t_1,t_2,\ldots,t_n$ $(1\leq t_1\leq t_2\leq\ldots\leq t_n\leq 10^9)$, where $t_i$ is the time when the $i$-th person arrives at the juice machine. If two people arrive at the same time, the order is determined from left to right according to the order given in the statement.

The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$, where $a_i$ is the volume requirement of the $i$-th person.

Output Format

If it is impossible to satisfy everyone, output $-1$.

Otherwise, output one integer in a single line, representing the minimum required sum of volumes.

5
1 3 4 6 6
3 8 2 7 4

24

5
1 3 4 5 5
3 8 2 7 4

26

Hint

The explanation for sample 1 is as follows.

The explanation for sample 2 is as follows.

Translated by ChatGPT 5