У Васи дома много устройств, которые работают от электричества. У него есть n сетевых фильтров, чтобы через них подключать устройства к электросети, i-ый сетевой фильтр имеет ai розеток.
Всего у Васи в квартире m устройств, а также k электрических розеток, к которым можно подключать сетевые фильтры или устройства напрямую. Конечно, сетевые фильтры можно подключать к другим сетевым фильтрам. Устройство (или сетевой фильтр) считается подключенным к электричеству, либо если оно подключено к одной из k электрических розеток, либо если оно подключено к какому-то подключенному к электричеству сетевому фильтру.
Какое минимальное количество сетевых фильтров из заданного набора понадобится Васе, чтобы подключить все имеющиеся устройства к электросети? Обратите внимание, что все устройства и сетевые фильтры при подключении занимают одну розетку и что к одной розетке можно подключить либо одно устройство, либо один сетевой фильтр.
Выходные данные
Выведите единственное целое число — минимальное количество сетевых фильтров, которое потребуется для подключения всех устройств. Если все устройства подключить невозможно, используя даже все сетевые фильтры, выведите -1.
Примечание
В первом тестовом примере можно подключить первый сетевой фильтр напрямую к электросети. После такого подключения получится 5 (3 на фильтре и 2 оставшиеся для подключения напрямую) свободных розеток для дальнейшего подключения к электросети. Таким образом, одного фильтра достаточно для подключения 5 устройств.
Один из оптимальных способов подключения во втором тестовом примере — подключить второй сетевой фильтр напрямую, а четвертый сетевой фильтр подключить в одну из розеток на втором сетевом фильтре. В таком случае получится ровно 7 (1 для подключения напрямую, 2 на втором фильтре, 4 на четвертом фильтре) свободных розеток для дальнейшего подключения к электросети. Используя один фильтр, подключить 7 устройств никак не получится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 3
3 1 2
|
1
|
|
2
|
4 7 2
3 3 2 4
|
2
|
|
3
|
5 5 1
1 3 1 2 1
|
-1
|