D. Евровидение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Организаторы музыкального конкурса Евровидение устали от экспериментов участников и опубликовали новый свод правил, которому необходимо следовать при сочинении песен:

  • длительность песни должна составлять ровно T секунд;
  • куплеты, припев и проигрыши должны исполняться целиком без пауз;
  • припев может быть исполнен сколько угодно раз (в том числе ноль), но каждый куплет и проигрыш — не более одного раза;
  • куплеты, припев и проигрыши можно исполнять в любом порядке, но никакие два куплета не должны исполняться подряд.

Группа уже сочинила припев длительностью A и N проигрышей с длительностями Si. Теперь группа планирует сочинить некоторое количество куплетов длительностью B, чтобы составить песню, удовлетворяющую всем правилам Евровидения. Какое минимальное количество куплетов ей необходимо сочинить?

Входные данные

В первой строке заданы три числа: требуемая длительность песни T (1 ≤ T ≤ 1018), длительность припева A и длительность куплетов B (1 ≤ A, B ≤ 500).

Во второй задано количество проигрышей N (0 ≤ N ≤ 500).

Если N > 0, то в последней строке заданы N чисел Si (1 ≤ Si ≤ 500) — длительности сочинённых проигрышей.

Все числа во входных данных целые.

Выходные данные

Минимальное количество куплетов, которые необходимо сочинить группе.

Если ни при каком количестве куплетов невозможно сочинить песню, удовлетворяющую всем правилам, выведите -1.

Примеры
Входные данные
100 11 20
3
13 7 24
Выходные данные
3
Входные данные
10 5 1
3
2 5 3
Выходные данные
0
Входные данные
8 9 2
2
1 2
Выходные данные
-1
Входные данные
10 3 10
0
Выходные данные
1
Примечание

В первом тесте можно составить песню из следующих частей: припев, куплет, припев, куплет, припев, куплет, второй проигрыш.

Во втором тесте возможны следующие решения — дважды припев; все проигрыши; припев и второй проигрыш и т.д.