| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 14 | 4 | 4 | 44.444% |
Давным давно, когда еще не было Бэтмена, Готэм-сити был очень дружным городом.
Но настали трудные времена. Несмотря на то, что дружба и единение всегда были и будут на вес золота, Готэм-сити распался на $n$ независимых друг от друга частей.
Бэтмен сразу понял, что такое состояние дел будет лишь на руку абсолютно всем злодеям, поэтому он решил попробовать воссоединить Готэм-сити.
Бэтмен хочет проложить $m$ двунаправленных дорог между частями Готэм-сити. Для каждой части известно, что суммарно из нее не может выходить более $deg_i$ дорог.
Заметьте, что Бэтмен может проложить более одной дороги между двумя частями Готэм-сити, но не может провести дорогу из части города в себя же!
Уровнем единения Готэм-сити Бэтмен считает как максимальное количество частей Готэма, таких что между каждыми двумя из них есть хотя бы одна дорога.
Помогите Бэтмену проложить дороги так, чтобы уровень единения Готэм-сити был максимально возможным!
В первой строке входных данных содержатся два целых числа $n$ и $m$ --- количество независимых частей и количество дорог, которые нужно проложить $(1 \leq n \leq 10^5),ドル $(0 \leq m \leq 10^5)$.
Во второй строке содержатся $n$ целых чисел $deg_i$ $(0 \leq deg_i \leq 10^5),ドル где $i$-ое число обозначает максимальное количество дорог, которое можно провести из независимой части с номером $i$.
В единственной строке выходного файла выведите единственное число --- максимально возможный уровень единения.
Если не существует способа проложить $m$ дорог так, чтобы не нарушать условия по максимальному число исходящих дорог ни для какой части города --- выведите -1.
4 3 1 2 3 4
3
3 100 3 3 3
-1
1 0 1
1