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

Условие

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

• сдвинуться влево на R_i клеток;
• сдвинуться вправо на R_i клеток;
• скушать пирожок.

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

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

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

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

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

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

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

Ограничения

 − 2 × 10⁴ ≤ D ≤ 2 × 10⁴

0 ≤ K ≤ 10

1 ≤ M ≤ 10

1 ≤ R_i ≤ 2 × 10⁴

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

4 1 2
2 10

3

1 5 1
3

-1

Разбор