Gloves

Limit pamięci: 64 MB

W ciemnej piwnicy domu znanego chemika, profesora Bajkwasa, znajdują się dwie szuflady pełne rękawiczek - jedna z lewymi, a druga z prawymi rękawiczkami. W każdej z nich są rękawiczki w różnych kolorach. Profesor wie, ile rękawiczek każdego koloru znajduje się w każdej z szuflad (liczba rękawiczek danego koloru może być różna w różnych szufladach). Jest także pewien, że możliwe jest znalezienie pary rękawiczek tego samego koloru.

Eksperyment Bajkwasa może się powieść tylko wtedy, gdy profesor użyje rękawiczek tego samego koloru (nie ma znaczenia którego), więc przed każdym doświadczeniem idzie on do piwnicy i bierze rękawiczki z szuflad, mając nadzieję, że znajdzie się wśród nich co najmniej jedna para w tym samym kolorze. W piwnicy jest bardzo ciemno i nie ma możliwości rozpoznania koloru żadnej rękawiczki bez wychodzenia z piwnicy. Profesor nie chce chodzić do piwnicy więcej niż raz (gdyby nie było pary rękawiczek jednego koloru), nie lubi też przynosić niepotrzebnie wielu rękawiczek do laboratorium.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę kolorów, a następnie liczby rękawiczek w każdym z kolorów w każdej z szuflad,
• obliczy najmniejszą łączną liczbę rękawiczek, która musi być wniesiona do laboratorium, aby była pewność, że jest wśród nich co najmniej jedna para rękawiczek tego samego koloru (należy określić liczbę rękawiczek wziętych z każdej szuflady),
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę różnych kolorów. Kolory są ponumerowane od do . Drugi wiersz wejścia zawiera liczb całkowitych , gdzie to liczba rękawiczek -tego koloru w szufladzie z lewymi rękawiczkami. Wreszcie, trzeci wiersz wejścia zawiera liczb całkowitych , gdzie to liczba rękawiczek -tego koloru w szufladzie z prawymi rękawiczkami.

Dodatkowo, w testach wartych 40% punktów, i .

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą - liczbę rękawiczek, które należy wyjąć z szuflady z lewymi rękawiczkami. Drugi wiersz wyjścia także powinien zawierać jedną liczbę całkowitą - liczbę rękawiczek, które należy wyjąć z szuflady z prawymi rękawiczkami. Suma tych dwóch liczb powinna być możliwie najmniejsza. Jeśli istnieje wiele poprawnych wyników, Twój program powinien wypisać dowolny z nich.

Przykład

Dla danych wejściowych:

4
0 7 1 6
1 5 0 6

poprawną odpowiedzią jest:

2
8

Autor zadania: Martins Opmanis.