Задача F. В поисках Васи ≡

Условие

Мальчик Влад идёт в гости к своему другу Васе, который живёт в доме с N подъездами и M этажами. На каждом этаже каждого подъезда расположено одинаковое количество квартир. Влад помнит номер Васиной квартиры X (квартиры нумеруются с 1), но не помнит ни номер подъезда, ни этаж.

Васин дом необычен тем, что домофоны в нём установлены не на входах в подъезды, а на каждом этаже. Поэтому Влад не может просто посмотреть, сколько квартир имеется на этаже. Вместо этого он может, поднявшись на какой-либо этаж в одном из подъездов, набрать номер Васиной квартиры на домофоне и по его сигналу определить, находится ли эта квартира на текущем этаже.

У Влада есть K предположений насчет того, какое количество квартир может быть на одном этаже одного подъезда. Влад собирается вычислить для каждого из K предположений номер подъезда и номер этажа, зайти в соответствующий подъезд, подняться на этаж и позвонить в домофон, чтобы проверить, живёт ли здесь Вася. Перейти из одного подъезда в другой можно только через улицу (0 этаж). Влад может проверять свои предположения в любом порядке.

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

В примере 2 для 1-го и 2-го предположения Вася живёт на 10 этаже 1 подъезда, в то время как для 3-го предположения Вася будет жить на 7 этаже 1 подъезда. Влад может сначала подняться на 7 этаж 1 подъезда для проверки 3-го предположения, а потом подняться на 10 этаж этого же подъезда для проверки предположений 1 и 2.

В примере 3 для 1-го предположения количество квартир в доме будет равно 40, а для 2-го предположения — 60. Ни в том, ни в другом случае в доме не найдётся квартиры с номером 100.

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

Входной файл содержит целые числа N M X K — количество подъездов и этажей в доме Васи, номер его квартиры, количество предположений Влада. Далее следуют K различных целых чисел a_i — предположения Влада о количестве квартир на одном этаже одного подъезда дома Васи.

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

Выходной файл должен содержать единственное целое число — минимальное количество этажей, на которые Владу необходимо будет подняться, чтобы точно определить, где живёт Вася.

Если ни одно предположение Влада не позволяет определить, где живёт Вася, то выведите −1.

Ограничения

1 ≤ N, M ≤ 10⁴; 1 ≤ X ≤ 10⁶; 1 ≤ K ≤ 10⁵; 1 ≤ a_i ≤ 10⁵

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

10 10 100
2
1 10

20

10 10 100
3
10 11 15

10

2 10 100
2
2 3

-1