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.