Taksówki
Limit pamięci: 64 MB
Bajtazar chce przejechać taksówką z miejscowości Bajtodziura do miejscowości Bajtodół,
odległej od Bajtodziury o km.
W odległości km od Bajtodziury na trasie między tymi miastami znajduje się
baza taksówek dysponująca taksówkami,
ponumerowanymi od 1 do .
Taksówka numer ma zapas benzyny wystarczający na przejechanie km.
Bajtazar może się przesiadać, zmieniając taksówki.
Wszystkie taksówki wyruszają z bazy, ale nie muszą do niej wracać.
Twoim zadaniem jest sprawdzenie, czy można przewieźć Bajtazara z Bajtodziury do Bajtodołu,
a jeżeli tak, to jaka jest minimalna liczba taksówek, jakie należy wykorzystać.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite
, oraz (, ),
pooddzielane pojedynczymi odstępami.
Oznaczają one odpowiednio: odległość z Bajtodziury do Bajtodołu,
odległość z Bajtodziury do bazy taksówek oraz liczbę taksówek znajdujących się w bazie.
W drugim wierszu wejścia znajduje się liczb całkowitych
(), pooddzielanych pojedynczymi odstępami.
Liczba oznacza dystans (w km), jaki maksymalnie może przejechać taksówka numer .
W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek .
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą:
minimalną liczbę taksówek, którymi musi jechać Bajtazar, aby dostać się z Bajtodziury do Bajtodołu.
Jeżeli nie jest to możliwe, Twój program powinien wypisać liczbę 0.
Przykład
Dla danych wejściowych:
42 23 6
20 25 14 27 30 7
poprawną odpowiedzią jest:
4
Wyjaśnienie do przykładu:
Bajtazar może jechać kolejno taksówkami numer: 4, 5, 1 i 2.
Autorzy zadania: Krzysztof Diks, Wojciech Rytter.