Wojna [A]

Limit pamięci: 128 MB

Jaś gra ze Stasiem w Bajtocką Wojnę. Na początku rozgrywki każdy z graczy otrzymuje stos kart. Na każdej z kart zapisana jest jedna liczba. Gra toczy się w turach. W czasie tury każdy gracz wyciąga dwie karty z wierzchu swojej talii i podejmuje decyzję, którą z nich odrzucić, a którą przekazać przeciwnikowi (w każdym ruchu jedną z kart należy odrzucić, a drugą przekazać przeciwnikowi). Przeciwnik wkłada otrzymaną kartę pod spód swojej talii.

Gra kończy się w momencie, gdy obaj gracze mają po jednej karcie. Jeśli liczba zapisana na karcie Jasia to , a liczba na karcie Stasia jest równa , to Jaś otrzymuje punktów, a Staś punktów.

Zakładamy, że gracze grają optymalnie (maksymalizują swój wynik liczony zgodnie z powyższą regułą). Ile punktów uda się zdobyć Jasiowi?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę kart, które otrzymali gracze. W drugim wierszu znajduje się ciąg liczb całkowitych (), który opisuje kolejne karty w talii Jasia, począwszy od karty na wierzchu talii. Trzeci wiersz opisuje karty w talii Stasia, w analogicznym formacie.

Wyjście

Twój program powinien wypisać na wyjście jedną liczbę całkowitą - liczbę punktów, które zdobędzie Jaś, przy założeniu optymalnej gry obu graczy.

Przykład

Dla danych wejściowych:

4
5 3 7 2
2 8 3 4

poprawną odpowiedzią jest:

1

Autor zadania: Eryk Kopczyński.