Давным давно, когда еще не было Бэтмена, Готэм-сити был очень дружным городом.
Но настали трудные времена. Несмотря на то, что дружба и единение всегда были и будут на вес золота, Готэм-сити распался на n независимых друг от друга частей.
Бэтмен сразу понял, что такое состояние дел будет лишь на руку абсолютно всем злодеям, поэтому он решил попробовать воссоединить Готэм-сити.
Бэтмен хочет проложить m двунаправленных дорог между частями Готэм-сити. Для каждой части известно, что суммарно из нее не может выходить более degi дорог.
Заметьте, что Бэтмен может проложить более одной дороги между двумя частями Готэм-сити, но не может провести дорогу из части города в себя же!
Уровнем единения Готэм-сити Бэтмен считает как максимальное количество частей Готэма, таких что между каждыми двумя из них есть хотя бы одна дорога.
Помогите Бэтмену проложить дороги так, чтобы уровень единения Готэм-сити был максимально возможным!
В первой строке входных данных содержатся два целых числа n и m — количество независимых частей и количество дорог, которые нужно проложить (1 ≤ n ≤ 105), (0 ≤ m ≤ 105).
Во второй строке содержатся n целых чисел degi (0 ≤ degi ≤ 105), где i-ое число обозначает максимальное количество дорог, которое можно провести из независимой части с номером i.
В единственной строке выходного файла выведите единственное число — максимально возможный уровень единения.
Если не существует способа проложить m дорог так, чтобы не нарушать условия по максимальному число исходящих дорог ни для какой части города — выведите -1.
4 3
1 2 3 4
3
3 100
3 3 3
-1
1 0
1
1
Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 15. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 31 балл.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 3000. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 32 балла.
Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 37 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».