e-olymp
Competitions

Ukrainian Olympiad in Informatics, II Stage, I Round

I. Прикраси

У Потоколяндії всього є $n$ різних видів ялинкових прикрас, пронумерованих цілими числами від $1$ до $n$. Кількість прикрас $i$-го виду рівна $a_i$. Дідусик Морозик зібрав усі прикраси Потоколяндії в одну купу і витягатиме з неї по одній прикрасі випадковим чином. Набір витягнутих прикрас Дідусик вважає новорічно-красивим, якщо з прикрас набору можна утворити хоча б $k$ пар прикрас одного виду. Наприклад, використовуючи набір прикрас $\{1,2,1,2,1,1,3\}$ (тут однаковими числами позначено прикраси одного виду) можна утворити не більше ніж три пари прикрас одного виду~--- дві пари прикрас виду $1$ та одну пару прикрас виду $2$. Допоможіть Морозику дізнатись мінімальну кількість витягань прикрас з купи, за якої гарантовано буде витягнуто новорічно-красивий набір прикрас. Гарантується, що якщо Дідусик витягне всі прикраси з купи, то він зможе утворити хоча б $k$ пар прикрас одного виду. \InputFile Перший рядок містить два цілі числа $n$ та $k$ ($1\le n,k\le 10^5$). Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots,a_n$ ($1\le a_i\le 10^5$). \OutputFile Виведіть одне ціле число~--- відповідь на задачу. \Note У першому прикладі, якщо Дідусик витягне з купи $6$ будь-яких прикрас, він завжди матиме змогу утворити $2$ пари прикрас одного виду.
Time limit 1 second
Memory limit 256 MiB
Input example #1
3 2
4 2 1
Output example #1
6
Source Ukrainian Olympiad in Informatics 2021, II Stage, I Round