Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

У Васи дома много устройств, которые работают от электричества. У него есть n сетевых фильтров, чтобы через них подключать устройства к электросети, i-ый сетевой фильтр имеет ai розеток.

Всего у Васи в квартире m устройств, а также k электрических розеток, к которым можно подключать сетевые фильтры или устройства напрямую. Конечно, сетевые фильтры можно подключать к другим сетевым фильтрам. Устройство (или сетевой фильтр) считается подключенным к электричеству, либо если оно подключено к одной из k электрических розеток, либо если оно подключено к какому-то подключенному к электричеству сетевому фильтру.

Какое минимальное количество сетевых фильтров из заданного набора понадобится Васе, чтобы подключить все имеющиеся устройства к электросети? Обратите внимание, что все устройства и сетевые фильтры при подключении занимают одну розетку и что к одной розетке можно подключить либо одно устройство, либо один сетевой фильтр.

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

В первой строке заданы три целых числа n, m, k (1 ≤ n, m, k ≤ 50) — количество сетевых фильтров, количество устройств и количество розеток, к которым можно подключаться напрямую, соответственно. Во второй строке через пробел заданы целые числа a1, a2, ..., an (1 ≤ ai ≤ 50) — число ai означает количество розеток на i-ом сетевом фильтре.

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

Выведите единственное целое число — минимальное количество сетевых фильтров, которое потребуется для подключения всех устройств. Если все устройства подключить невозможно, используя даже все сетевые фильтры, выведите -1.

Примеры
Входные данные
3 5 3
3 1 2
Выходные данные
1
Входные данные
4 7 2
3 3 2 4
Выходные данные
2
Входные данные
5 5 1
1 3 1 2 1
Выходные данные
-1
Примечание

В первом тестовом примере можно подключить первый сетевой фильтр напрямую к электросети. После такого подключения получится 5 (3 на фильтре и 2 оставшиеся для подключения напрямую) свободных розеток для дальнейшего подключения к электросети. Таким образом, одного фильтра достаточно для подключения 5 устройств.

Один из оптимальных способов подключения во втором тестовом примере — подключить второй сетевой фильтр напрямую, а четвертый сетевой фильтр подключить в одну из розеток на втором сетевом фильтре. В таком случае получится ровно 7 (1 для подключения напрямую, 2 на втором фильтре, 4 на четвертом фильтре) свободных розеток для дальнейшего подключения к электросети. Используя один фильтр, подключить 7 устройств никак не получится.