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.