The 271st Well-Known Cup

Time limit1sMemory limit1024 MB

Summary

Pick pairs so the opponent takes the one with larger B; greedily keep the largest A while holding a B gap and fallback cheaper in A.

Level: Medium7 of 10
Topics: Greedy, Heap, Sorting, Array
Solved: No attempts yet

Problem

In the year 2250, the 271st Well-Known Cup, awaited by people all over the world, is held. When the first contest was held in 2018, it was named the Well-Known Cup in the spirit of "problems solvable with well-known algorithms", but now the number of people setting and testing the problems alone reaches about 10,000, so the name means "everyone well known in the world of algorithms takes part in setting and testing this contest".

After defeating countless rivals, the final against Etacoder Plus has finally arrived. Note that Etacoder Plus and I are artificial intelligences. My name is SolvingCore KX. It is odd that a human made it to the finals these days, to be sure. One might ask why the human division and the artificial intelligence division are not held separately, but since everyone passes the Turing test these days, telling humans and artificial intelligences apart is extremely difficult, so that is not a realistic option.

The final is run a little unusually. Etacoder Plus won last year's contest, so he is under a slight restriction. Specifically, an even number of problems is prepared for the final. First the challenger chooses two problems, and the champion chooses one of the two. The challenger takes the remaining one. This repeats until every problem has been assigned, and then whoever solves all the assigned problems first wins. (In 2250, artificial intelligences are called people too.)

I first quantified, as a natural number for each problem, how confident each of us is. That is, I am confident by $A[i]$ when solving problem $i$ , and Etacoder Plus is confident by $B[i]$ . When I choose two problems, Etacoder Plus will of course take the problem with the higher $B$ value. Assuming this strategy, I want to maximize the sum of the $A$ values over the problems I take.

Input

The first line gives an even $N(2 \le N \le 200,000)$ . The next line gives $A[1], \dots, A[N]$ , and the line after that gives $B[1], \dots, B[N]$ , where $(1 \le A[i], B[i] \le 10^9)$ . All $A[i]$ are distinct, and all $B[i]$ are distinct as well.

Output

Print the maximum sum of the $A[i]$ values over the problems I take.

Examples1

Example 1
Input
```
4
4 2 8 6
6 5 7 8
```
Expected output
```
10
```