Объединение Готэм-сити

시간 제한2초메모리 제한1024 MB

요약

각 부분의 차수 상한 deg_i와 정확히 m개의 간선이 주어질 때, 자기 자신으로 가는 간선 없이 다중 간선을 허용하며 최대 크기의 클리크를 만들고, 배치가 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Давным давно, когда еще не было Бэтмена, Готэм-сити был очень дружным городом.

Но настали трудные времена. Несмотря на то, что дружба и единение всегда были и будут на вес золота, Готэм-сити распался на $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.

예제3

예제 1
입력
```
4 3
1 2 3 4
```
예상 출력
```
3
```
예제 2
입력
```
3 100
3 3 3
```
예상 출력
```
-1
```
예제 3
입력
```
1 0
1
```
예상 출력
```
1
```