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.