Автор: | А. Усманов | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Мальчик Влад идёт в гости к своему другу Васе, который живёт в доме с 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 различных целых чисел ai — предположения Влада о количестве квартир на одном этаже одного подъезда дома Васи.
Выходной файл должен содержать единственное целое число — минимальное количество этажей, на которые Владу необходимо будет подняться, чтобы точно определить, где живёт Вася.
Если ни одно предположение Влада не позволяет определить, где живёт Вася, то выведите − 1.
1 ≤ N, M ≤ 104; 1 ≤ X ≤ 106; 1 ≤ K ≤ 105; 1 ≤ ai ≤ 105
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|