Путешествие из Петербурга в Москву ≡

Автор:	Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков		Ограничение времени:	5 сек
Входной файл:	input.txt		Ограничение памяти:	200 Мб
Выходной файл:	output.txt

Условие

Профессор едет по шоссе из Петербурга в Москву, имея при себе карту с указанием всех N стоящих на шоссе бензоколонок и расстояний D_i до них от Петербурга. Известно расстояние S, которое может проехать машина с полностью заправленным баком.

Требуется выяснить, на каких бензоколонках нужно заправляться, чтобы количество заправок было минимально. В начале пути бак полон.

Расстояние от Петербурга до Москвы равно L.

Формат входного файла

Во входном файле сначала указаны числа L, S, N, после чего перечислено N чисел D_i.

Формат выходного файла

Выходной файл должен содержать единственное число - минимальное количество заправок. Если добраться из Петербурга в Москву невозможно, следует вывести число -1.

Ограничения

0 <= L <= 10^9

0 <= S <= 10^9

0 <= N <= 500000

0 <= D_i <= L

Все числа целые.

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	100 60 2 50 30 скопировать	1 скопировать
2	100 30 3 60 20 50 скопировать	-1 скопировать

---