Задача B. Шалтай-Болтай

Автор:С. Пак, И. Туфанов   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Шалтай-Болтай очень любит ходить по своей стене в разные стороны и кушать пирожки. Сверху стена выглядит как длинная полоска из одинаковых клеток, пронумерованных по возрастанию слева направо. Каждый день Шалтай-Болтай может выполнить одно из трёх действий:

Число клеток Ri зависит от текущего дня недели. Шалтай-Болтай считает, что в неделе M дней.

В начальный момент времени Шалтай-Болтай находится на клетке с номером ноль, имеет K пирожков и считает, что сейчас первый день недели.

Требуется найти минимальное количество дней Q, через которое он может оказаться в клетке с номером D, или определить, что это невозможно.

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

Во входном файле содержатся числа D K M. Далее следует M целых чисел Ri — количество клеток, на которое Шалтай может сдвинуться в i-й день недели.

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

В выходном файле должно содержаться единственное число Q, либо  − 1, если добраться до клетки D невозможно.

Ограничения

 − 2 × 104 ≤ D ≤ 2 × 104

0 ≤ K ≤ 10

1 ≤ M ≤ 10

1 ≤ Ri ≤ 2 × 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2
2 10
3
2
1 5 1
3
-1

Разбор

Динамика 3 измерения.

0.132s 0.021s 13