Батарейки

У день змагань у лабораторії використовується $n$ комп'ютерів. Нажаль, електрику відключено, і комп'ютери можуть працювати лише від батарей. Технічний персонал змагання розпоряджається $m$ батареями. $i$-та батарея дозволяє будь-якому комп'ютеру працювати $a_i$ хвилин.

Спочатку вони можуть вмістити не більше однієї батареї на комп'ютер. Після цього в будь-який момент з будь-якого комп'ютера можна вийняти поточну батарею і вставити іншу. Вставлена батарея може бути новою або знятою з іншого комп'ютера. Можете вважати, що процес вийняття і встановлення батарей не займає часу. Також зверніть увагу, що батареї не перезаряджаються.

Щоб визначити тривалість змагання, організатори хочуть знати максимальну кількість хвилин, протягом яких усі комп'ютери можуть використовуватися одночасно. Технічному персоналу визначити це досить складно. Допоможіть їм у цьому.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m(1\le n\le m\le 10^5)$ — кількість комп'ютерів і батарей відповідно. Наступний рядок містить $m$ цілих чисел $a_1,a_2,...,a_m(1\le a_i\le 10^9,1\le i\le m)$ — ємність батарей.

Вихідні дані

Виведіть ціле число — максимальну кількість хвилин, протягом яких всі комп'ютери можуть працювати одночасно.

Приклади

У цьому прикладі є $2$ комп'ютери та $3$ батареї. Кожна батарея має ємність $3$ хвилини. Спочатку помістимо першу і другу батарейки в перший і другий комп'ютер відповідно. Через $2$ хвилини вийміть батарею з першого комп'ютера і вставте третю батарею (ще повністю заряджену) в перший комп'ютер. По закінченню $3$-ї хвилини батарея в другому комп'ютері розрядиться, давайте витягнемо її і замінимо на першу батарею, яку ми витягли з першого комп'ютера, у якої ще залишилася $1$ хвилина. По закінченню $4$-ї хвилини ця батарея також розрядиться. Хоча заряд батареї першого комп'ютера наразі залишився $1$ хвилина, інші батареї вже розрядилися, і ми не можемо більше підтримувати роботу обох комп'ютерів.

Оцінювання

Ця задача складається з $5$-х підзадач. Бали за підзадачу нараховуються лише у випадку успішного проходження всіх тестів, пов'язаних з цією підзадачею.

1. ($5$ балів): $a_i=1$;

2. ($6$ балів): $n=m$;

3. ($14$ балів): $a_i\le 2$;

4. ($17$ балів): $n=2$;

5. ($58$ балів): $немаєдодатковихобмежень$;