408308: GYM103091 H War

Alice and Bob are competing to determine the champion of the annual Stanford vs. Berkeley Card Tournament. They are playing a modified version of the card game War.

The game works as follows: A deck of $$$2N$$$ cards numbered $$$1$$$ to $$$2N$$$ (no suites) are shuffled and dealt so Alice and Bob each have $$$N$$$ cards, face down. Alice and Bob take the top cards of their stacks and turn them face up at the same time. Whoever plays the card with the higher number wins a point. Both cards played are then discarded. Alice and Bob repeat this process until they have no cards remaining. The winner of the game is the player with the most points.

Just before the game starts, Bob leaves the room to turn in his CS homework. Alice takes advantage of this opportunity to look at her stack of cards and Bob's stack. She can re-order the cards in her stack and Bob's stack, but she cannot move cards from her stack to Bob's, or vice-versa. Given her stack and Bob's stack, what is the most number of points she can win after re-ordering the cards?

The first line of the input is a single integer, $$$N$$$ ($$$1 \leq N \leq 10^5$$$). The second line is a list of $$$N$$$ integers separated by spaces, representing Alice's stack of cards. The third line is a list of $$$N$$$ integers separated by spaces, representing Bob's stack of cards. All natural numbers from 1 to $$$2N$$$, inclusive, will be present exactly once in the second or third line.

The output should be one line with an integer which is the most number of points Alice can win after re-ordering her and Bob's stacks.

10
1 3 5 7 9 11 13 15 17 19
2 4 6 8 10 12 14 16 18 20

9

8
2 7 10 8 5 4 6 15
3 9 14 11 12 13 1 16

4