Odważniki
Limit pamięci: 32 MB
Bajtocki Instytut Fizyki Doświadczalnej przy przeprowadzce do nowego budynku
napotkał na nie lada problem logistyczny -
kłopotliwe okazało się przeniesienie bogatej kolekcji precyzyjnych
odważników.
Instytut ma do dyspozycji pewną liczbę kontenerów, każdy o ograniczonej
wytrzymałości.
Należy pomieścić w nich jak najwięcej odważników, gdyż pozostałe,
niestety, będzie trzeba wyrzucić.
Do każdego z kontenerów można włożyć dowolnie wiele odważników,
ale nie wolno przekroczyć przy tym jego wytrzymałości.
Kontener może również pozostać pusty.
Dowolne dwa odważniki w Instytucie mają ciekawą własność:
masa jednego z nich jest zawsze wielokrotnością masy
drugiego z nich.
W szczególności, oba odważniki mogą mieć równe masy.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia wytrzymałości kontenerów
i masy odważników,
-
wyznaczy maksymalną liczbę odważników, jakie można pomieścić
w kontenerach,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
oraz (), oddzielone pojedynczym
odstępem i oznaczające odpowiednio: liczbę kontenerów i liczbę
odważników.
Drugi wiersz wejścia zawiera liczb całkowitych
( dla ),
pooddzielanych pojedynczymi odstępami i oznaczających
wytrzymałości kontenerów, wyrażone w miligramach.
W trzecim wierszu wejścia znajduje się liczb całkowitych
( dla ),
pooddzielanych pojedynczymi odstępami i oznaczających masy
odważników, również wyrażone w miligramach.
Wyjście
Pierwszy i jedyny wierszy wyjścia powinien zawierać jedną
liczbę całkowitą - największą liczbę odważników, jakie można
porozmieszczać w kontenerach bez przekroczenia ich wytrzymałości.
Przykład
Dla danych wejściowych:
2 4
13 9
4 12 2 4
poprawną odpowiedzią jest:
3
W kontenerach można umieścić dowolne trzy z czterech odważników, ale
nie można umieścić wszystkich odważników.
Autor zadania: Jakub Radoszewski.