지훈 apprécie depuis peu un jeu de cartes solitaire.
Chaque carte porte un entier strictement positif ; plusieurs cartes peuvent porter le même nombre.
On commence par mélanger aléatoirement un nombre pair de cartes, puis on les partage en deux piles de même taille, l’une à gauche et l’autre à droite.
On prépare également un récipient vide.
On joue ensuite en comparant les cartes au sommet des deux piles.
Les règles sont les suivantes. La carte au sommet de la pile gauche sera appelée carte gauche, et celle au sommet de la pile droite carte droite.
(1) À tout moment, on peut jeter dans le récipient seulement la carte gauche ou les deux cartes. Cela ne rapporte aucun point.
(2) Si le nombre sur la carte droite est inférieur à celui sur la carte gauche, on peut aussi jeter seulement la carte droite.
Jeter seulement la carte droite rapporte autant de points que le nombre qu’elle porte.
(3) On poursuit selon les règles (1) et (2). Dès qu’une des piles ne contient plus de cartes, la partie se termine,
et la somme des points obtenus jusque-là constitue le score final.
L’exemple suivant commence avec deux piles de trois cartes chacune.
Au départ, la carte droite 2 est inférieure à la carte gauche 3,
on peut donc, selon la règle (1), jeter seulement la carte gauche ou les deux cartes,
ou, selon la règle (2), seulement la carte droite.
Si l’on jette seulement la carte droite 2, on gagne 2 points et on jette cette carte.
La nouvelle carte au sommet de la pile droite est 4, supérieure à la carte gauche 3,
on peut donc, selon la règle (1), jeter seulement la carte gauche ou les deux cartes.
Si l’on jette les deux, la carte gauche devient 2 et la carte droite 1.
Les règles (1) et (2) permettent à nouveau de choisir entre trois actions ;
si l’on jette seulement la carte gauche, la carte gauche devient 5 et la carte droite reste 1.
Les règles (1) et (2) permettent encore de choisir entre trois actions ;
si l’on jette seulement la carte droite, on gagne 1 point et on jette la carte droite 1.
La pile droite est maintenant vide ; la partie se termine donc selon la règle (3), avec un score final de $2+1=3$.
Écrivez un programme qui, étant données les deux piles, affiche le score final maximal possible.
Dans l’exemple ci-dessus, le score final maximal vaut 7.
Entrée
La première ligne de l’entrée standard contient un entier strictement positif $N$ ($1\le N\le2{,}000$), le nombre de cartes d’une pile.
La ligne suivante contient les $N$ entiers $A$ ($1\le A\le2{,}000$) des cartes de la pile gauche, dans l’ordre des cartes.
La ligne suivante contient les $N$ entiers $B$ ($1\le B\le2{,}000$) des cartes de la pile droite, dans l’ordre des cartes.
Chaque pile peut contenir au moins deux cartes portant le même nombre.
Sortie
Affichez sur la sortie standard le score final maximal possible.
Exemples
Entrée 1
3 3 2 5 2 4 1
Sortie 1
7
Entrée 2
4 1 2 3 4 4 1 2 3
Sortie 2
6
Sous-tâches
31 points : $N\le10$.
33 points : $N\le25$.
36 points : aucune contrainte supplémentaire.