Card Game

Jihun plays a solitaire card game. Each card has one positive integer written on it, and several cards may carry the same number. To set up, shuffle an even number of cards, split them into two piles of the same size, and put one pile on the left and the other on the right. Next to them, put an empty bin for discarded cards.

You play by comparing the top cards of the two piles. Call the top card of the left pile the left card, and the top card of the right pile the right card. The rules are:

1. At any time you may throw the left card into the bin, or throw the left card and the right card into the bin together. Neither move scores anything.
2. If the number on the right card is smaller than the number on the left card, you may throw only the right card into the bin. That move scores the number written on the right card.
3. Play under rules 1 and 2 until one of the piles has no cards left. The game ends there, and the points collected so far add up to the final score.

The setup below starts with three cards in each pile.

At the start the right card 2 is smaller than the left card 3, so rule 1 allows throwing away the left card or both cards, and rule 2 allows throwing away only the right card. Throwing away only the right card scores 2 points. The right card is now 4, which is larger than the left card 3, so only the two moves of rule 1 remain. Throwing both away leaves the left card 2 and the right card 1. Throwing away only the left card there leaves the left card 5 and the right card 1. Throwing away only the right card then scores 1 point, the right pile is empty, and rule 3 ends the game. Those choices give a final score of $2 + 1 = 3$. Playing the same setup as well as possible gives a final score of 7.

Write a program that prints the largest final score reachable from the two given piles.

The first line has the number of cards in one pile, $N$ ($1 \le N \le 2000$). The second line has the $N$ integers $A$ ($1 \le A \le 2000$) written on the cards of the left pile, starting from the top card. The third line has the $N$ integers $B$ ($1 \le B \le 2000$) written on the cards of the right pile, starting from the top card. One pile may hold two or more cards with the same number.

Print the largest final score you can reach.