Odważniki
Limit pamięci: 32 MB
Bajtek otrzymał na gwiazdkę zestaw składający się z czarnych odważników,
szarych odważników oraz bardzo lekkich wag szalkowych.
Zachwycony nową zabawką, Bajtek szybko ułożył pewną konstrukcję.
Najpierw położył na podłodze wagę, następnie
po jednej stronie wagi położył pewien czarny odważnik, a po drugiej
następną wagę i tak na kolejnych wagach stawiał z jednej strony kolejne
czarne odważniki, a z drugiej kolejne wagi i tak dalej.
Na ostatniej, -tej wadze, położył z jednej strony
ostatni czarny odważnik, a drugą stronę pozostawił pustą.
Teraz Bajtek wymyślił pewną łamigłówkę.
Na ostatnim pustym miejscu można położyć dowolny szary odważnik.
Jeśli pewna waga szalkowa będzie wtedy w równowadze,
to można ją wymienić wraz ze wszystkim, co się na niej znajduje,
na jeden szary odważnik o tej samej łącznej masie, o ile taki jest dostępny.
Zakładamy tu, że masa wag szalkowych jest pomijalnie mała.
Bajtek chce na samym końcu mieć jak najmniej odważników,
aby swoją konstrukcję mógł bez problemu przesłać pocztą do swojej przyjaciółki Bitoasi.
Znajdź najmniejszą liczbę odważników, jakie Bajtek może pozostawić w konstrukcji.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba
całkowita () oznaczająca liczbę wag szalkowych.
W drugim wierszu znajduje się liczb całkowitych
() pooddzielanych pojedynczymi odstępami, oznaczających
masy czarnych odważników stojących na kolejnych wagach.
W trzecim wierszu znajduje się liczb całkowitych
() pooddzielanych pojedynczymi odstępami, oznaczających
masy szarych odważników.
Możesz założyć, że w testach wartych co najmniej punktów, masy odważników
nie przekraczają , oraz zachodzi warunek .
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę
całkowitą - minimalną liczbę odważników, jaką można pozostawić w konstrukcji.
Przykład
Dla danych wejściowych:
3
10 6 2
2 4 12
poprawną odpowiedzią jest:
2
Autor zadania: Jacek Tomasiewicz.