D2. Кофе и курсовая работа (сложная версия)
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между легкой и сложной версиями — ограничения.

Поликарпу нужно написать курсовую работу. Курсовая работа состоит из $$$m$$$ страниц.

У Поликарпа также есть $$$n$$$ чашек кофе. Кофе в $$$i$$$-й чашке содержит $$$a_i$$$ кофеина. Поликарп может выпить некоторые чашки кофе (каждую не более одного раза). Он может пить чашки в любом порядке. Поликарп пьет каждую чашку мгновенно и полностью (то есть он не может разделить какую-либо чашку на несколько дней).

Конечно же, курсовые работы не всегда пишутся за один день (по крайней мере в идеальном мире Берляндии). Некоторые из них требуют множества дней упорного труда.

Рассмотрим какой-нибудь день работы Поликарпа. Пусть Поликарп выпил $$$k$$$ чашек кофе, а количества кофеина в чашках, которые Поликарп выпил в течение этого дня, равны $$$a_{i_1}, a_{i_2}, \dots, a_{i_k}$$$. Тогда первая чашка, которую он выпьет, даст ему энергию на написание $$$a_{i_1}$$$ страниц курсовой работы, вторая чашка даст ему энергию на написание $$$max(0, a_{i_2} - 1)$$$ страниц, третья чашка даст ему энергию на написание $$$max(0, a_{i_3} - 2)$$$ страниц, ..., и $$$k$$$-я чашка даст ему энергию на написание $$$max(0, a_{i_k} - k + 1)$$$ страниц.

Если Поликарп не пьет кофе в течение какого-либо дня, то он вообще не может писать курсовую работу в течение этого дня.

Поликарп хочет закончить курсовую работу настолько рано, насколько это возможно (потратить минимальное количество дней на это). Ваша задача — найти это количество дней или сказать, что это невозможно.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — количество чашек кофе и количество страниц в курсовой работе.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равно количеству кофеина, содержащегося в $$$i$$$-й чашке.

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

Если написать курсовую работу невозможно, выведите -1. Иначе выведите минимальное количество дней, необходимое Поликарпу для того, чтобы сделать это.

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

В первом тестовом примере Поликарп может выпить четвертую чашку в течение первого дня (и написать $$$1$$$ страницу), первую и вторую чашки в течение второго дня (и написать $$$2 + (3 - 1) = 4$$$ страницы), пятую чашку в течение третьего дня (и написать $$$2$$$ страницы) и третью чашку в течение четвертого дня (и написать $$$1$$$ страницу), таким образом, ответ равен $$$4$$$. Очевидно, что невозможно написать курсовую за три дня или быстрее.

Во втором тестовом примере Поликарп может выпить третью, четвертую и вторую чашки в течение первого дня (и написать $$$4 + (2 - 1) + (3 - 2) = 6$$$ станиц) и шестую чашку в течение второго дня (и написать $$$4$$$ страницы), таким образом, ответ равен $$$2$$$. Очевидно, что Поликарп не может написать курсовую работу полностью за один день в этом тесте.

В третьем тестовом примере Поликарп может выпить все чашки кофе в течение первого дня и написать $$$5 + (5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 15$$$ страниц курсовой работы.

В четвертом тестовом примере Поликарп не может выпить все чашки кофе в течение первого дня и должен выпить одну из них в течение второго дня. Таким образом, В течение первого дня он напишет $$$5 + (5 - 1) + (5 - 2) + (5 - 3) = 14$$$ страниц курсовой работы, а в течение второго дня он напишет $$$5$$$ страниц курсовой работы. Этого достаточно, чтобы завершить ее.

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