Прикраси#10267
У Потоколяндії всього є різних видів ялинкових прикрас, пронумерованих цілими числами від до . Кількість прикрас -го виду рівна a_i.
Дідусик Морозик зібрав усі прикраси Потоколяндії в одну купу і витягатиме з неї по одній прикрасі випадковим чином. Набір витягнутих прикрас Дідусик вважає новорічно-красивим, якщо з прикрас набору можна утворити хоча б пар прикрас одного виду. Наприклад, використовуючи набір прикрас \{1,2,1,2,1,1,3\} (тут однаковими числами позначено прикраси одного виду) можна утворити не більше ніж три пари прикрас одного виду — дві пари прикрас виду та одну пару прикрас виду .
Допоможіть Морозику дізнатись мінімальну кількість витягань прикрас з купи, за якої гарантовано буде витягнуто новорічно-красивий набір прикрас. Гарантується, що якщо Дідусик витягне всі прикраси з купи, то він зможе утворити хоча б пар прикрас одного виду.
Перший рядок містить два цілі числа та (1\le n,k\le 10^5).
Другий рядок містить цілих чисел a_1,a_2,\dots,a_n (1\le a_i\le 10^5).
Виведіть одне ціле число — відповідь на задачу.
Приклад 1
У першому прикладі, якщо Дідусик витягне з купи будь-яких прикрас, він завжди матиме змогу утворити пари прикрас одного виду.