409742: GYM103715 C Контроль сахара

C. Контроль сахараограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Владелец магазина «Тингам» столкнулся с проблемой. К нему в магазин пришли $$$n$$$ человек и всем нужен сахар: $$$i$$$-й ($$$1 \le i \le n$$$) хочет купить $$$a_i$$$ килограмм сахара. Владелец магазина не понимает зачем людям столько сахара, но он точно знает, что всем покупателям сахара не хватит, потому что у него в магазине есть только $$$m$$$ килограмм сахара. Если какой-то покупатель не сможет купить сахар, он расстроится и больше не будет ходить в магазин «Тингам».

Владелец магазина не хочет терять клиентов. Чтобы сахара хватило всем, он решил установить ограничение $$$k$$$ — максимальное количество килограмм сахара, которое может купить один человек. Таким образом, когда $$$i$$$-й ($$$1 \le i \le n$$$) человек приходит в магазин он покупает $$$min(a_i, k)$$$ килограмм сахара (не больше чем ему нужно, но и не больше чем $$$k$$$ килограмм).

Владелец магазина хочет продать как можно больше сахара. Помогите хозяину магазина и найдите такое $$$k$$$, при котором каждому покупателю достанется $$$min(a_i, k)$$$ килограмм сахара и при этом суммарное количество проданного сахара будет максимальным, но не будет превышать запаса сахара в магазине $$$m$$$.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5, n \le m < \sum_{i=1}^n a_i$$$) — количество покупателей и количество килограмм сахара, которое есть в магазине соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 10^9, \sum_{i=1}^n a_i > n$$$). Число $$$a_i$$$ — количество килограмм сахара, которое хочет купить $$$i$$$-й покупатель.

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

Выведите одно число $$$k$$$, при котором каждому покупателю достанется $$$min(a_i, k)$$$ килограмм сахара и при этом суммарное количество проданного сахара будет максимальным, но не будет превышать запаса сахара в магазине $$$m$$$. Гарантируется, что такое $$$k$$$ всегда найдётся.

ПримерыВходные данные

5 12
3 1 4 2 5

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

3

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

2 17
23 65

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

8

Примечание

В первом примере необходимо установить ограничение $$$k = 3$$$. Таким образом клиенты купят $$$3 + 1 +3 + 2 + 3 = 12$$$ килограмм сахара. Ответы $$$2$$$ и $$$4$$$ неверные, так как при $$$k = 2$$$ клиенты купят меньше сахара чем при $$$k = 3$$$, а при $$$k = 4$$$ один из клиентов не сможет купить $$$min(a_i, k)$$$ килограмм сахара.

Во втором примере $$$k = 8$$$ и клиенты суммарно купят $$$16$$$ килограмм сахара.