H. Juice
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a juicer that can make a cup of juice of any volume per minute.

There are $$$n$$$ people lined up. The $$$i$$$-th person will walk to the juicer at the $$$t_i$$$-th minute and take the largest cup of juice that has been made so far. The $$$i$$$-th person will be satisfied if they get a cup of juice with a volume greater than or equal to $$$a_i$$$. If there is no juice at that time, the $$$i$$$-th person will also be unsatisfied.

Determine if it is possible to satisfy all the people. If so, output the minimum total volume of juice needed to satisfy everyone.

Input

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

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$$$ represents the time when the $$$i$$$-th person arrives at the juicer. If two people arrive at the same time, the order is determined from left to right as given in the input.

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

Output

If it is not possible to satisfy all the people, output $$$-1$$$.

Otherwise, output a single integer representing the minimum total volume needed.

Examples
Input
5
1 3 4 6 6
3 8 2 7 4
Output
24
Input
5
1 3 4 5 5
3 8 2 7 4
Output
26
Note

Explanation for Example 1:

TimeProductionTaken
$$$1$$$$$$3$$$$$$3$$$
$$$2$$$——
$$$3$$$$$$8$$$$$$8$$$
$$$4$$$$$$2$$$$$$2$$$
$$$5$$$$$$4$$$—
$$$6$$$$$$7$$$$$$7,4$$$

Explanation for Example 2:

TimeProductionTaken
$$$1$$$$$$3$$$$$$3$$$
$$$2$$$$$$4$$$—
$$$3$$$$$$8$$$$$$8$$$
$$$4$$$$$$4$$$$$$4$$$
$$$5$$$$$$7$$$$$$7,4$$$
$$$6$$$——