Office's biscuits

ENGLISH

Task condition

• Time limit,s => 1
• Memory Limit,MB => 64

Task

Developer Fyodor loves biscuits in the office very much, and he knows exactly all the N places where they can be found, as well as the exact number of Cn biscuits in each place. Today Fyodor is especially hungry, he has finished a big task, and decides to allocate himself M hours to eat all the biscuits in the office.

Fyodor calculated the minimum number of biscuits K that he needs to eat within an hour so that in the end he has time to eat all the biscuits in the office in the allotted time or earlier.

At any hour, he can visit any one place with biscuits and eat K biscuits in this place, he will spend an hour on it, even if there are less than K biscuits left in this place, because he will discuss tasks and plans with colleagues. Fyodor may not visit places without biscuits.

Colleagues, out of respect for Fyodor, never touch his favorite biscuits.

Input data (received in the standard input stream)

The first line is integers N and M separated by a space (1≤N≤100 000, 1≤M≤200 000)

Then there are N lines, on each of which there is one integer Cn (0≤Cn≤10,000)

All the input data of our tests always comply with the specified parameters, no additional checks are required.

Output data (expected in standard output stream)

One integer, the minimum possible K. Either 0 if there are no biscuits in the office, or if Fyodor does not have time to eat all the biscuits in the allotted time.

Example:

exp 1

input: 3 6 4 4 4 output: 2 A simple example to familiarize yourself with the input and output data

exp 2

input: 3 6 4 4 5 output: 3 There is a similar situation here, but eating 2 biscuits, Fyodor will not have time to eat the last one

exp 3

input: 3 3 4 4 8 output: 8 Boundary situation at N = M

Notes:

It is possible to use only standard language libraries, installation and use of additional libraries are not possible.

===================================================================================

Русский

Условие задачи

• Ограничение времени, с => 1
• Ограничение памяти, МБ => 64

Задача

Разработчик Фёдор очень любит печеньки в офисе, и он точно знает все N мест, где их можно найти, а также точное количество печенек Сn в каждом месте. Сегодня Фёдор особенно голоден, он закончил большую задачу, и решает выделить себе M часов на то, чтобы съесть все печеньки в офисе.

Фёдор рассчитал минимальное количество печенек K, которое ему нужно съедать в течение часа так, чтобы в итоге успеть съесть все печеньки в офисе за выделенное время или раньше.

В каждый час, он может посетить одно любое место с печеньками и съесть K печенек в этом месте, он потратит на это целый час, даже если в этом месте осталось меньше, чем K печенек, потому что будет обсуждать с коллегами задачи и планы. Места без печенек Фёдор может не посещать.

Коллеги, из уважения к Фёдору, никогда не трогают его любимые печеньки

Входные данные (поступают в стандартный поток ввода)

Первая строка - целые числа N и M через пробел (1≤N≤100 000, 1≤M≤200 000)

Далее N строк, на каждой из которых одно целое число Cn (0≤Cn≤10 000)

Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются

Выходные данные (ожидаются в стандартном потоке вывода)

Одно целое число, минимально возможное K. Либо 0, если в офисе нет печенек, или если Фёдор не успеет съесть все печеньки за выделенное время.

Примеры:

Пример 1

Ввод: 3 6 4 4 4 Вывод: 2 Простой пример для ознакомления с входными и выходными данными

Пример 2

Ввод: 3 6 4 4 5 Вывод: 3 Здесь похожая ситуация, но съедая по 2 печеньки, Фёдор не успеет съесть последнюю

Пример 3

Ввод: 3 3 4 4 8 Вывод: 8 Граничная ситуация при N = M

Примечания по оформлению решения:

Возможно использование только стандартных библиотек языков, установки и использование дополнительных библиотек невозможны.