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.