Задача G. Путешествие из Петербурга в Москву

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

Условие

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

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

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

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

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

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

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

Ограничения

0 <= L <= 10^9

0 <= S <= 10^9

0 <= N <= 500000

0 <= Di <= L

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 60 2
50 30
1
2
100 30 3
60 20 50 
-1

0.033s 0.007s 15