Пари камінців

У Аліси та Боба є $n$ купок з камінцями, пронумерованих від $1$ до $n$. У $i$-ій купці $a_i$ камінців. Вони виконують наступний процес:

1. Аліса вибирає дві непусті купки. Нехай у них $x$ та $y$ камінців відповідно.

2. Аліса забирає по одному камінцю з цих купок.

3. Далі Боб теж вибирає дві непусті купки так, щоб у них також було $x$ та $y$ камінців відповідно. Тобто Боб вибирає дві купки так, щоб у них була така ж кількість камінців, як було початково у купках Аліси. Бобу дозволяється вибирати купки, які вибрала Аліса. Якщо він це зробити не може, то процес закінчується.

4. Боб також забирає по одному камінцю з вибраних ним купок.

5. Якщо кількість непорожніх купок менша за $2$, то описаний процес закінчується, інакше знову повторюється спочатку.

Зверніть увагу, що Аліса не зобов'язана вибирати кожного разу одні й ті ж самі значення $x$ та $y$.

Аліса і Боб хочуть зробити так, щоб у купках залишилось якнайменше камінців. Зауважте, що в них спільна мета. Допоможіть їм знайти мінімальну кількість камінців, які можуть залишитися.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $g$ ($2\le n\le 2\cdot 10^5$, $0\le g\le 5$) — кількість купок та номер блока.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — кількість камінців у кожній купці.

Вихідні дані

Виведіть одне число — відповідь на задачу.

Приклади

Примітка

У першому прикладі Аліса може спочатку вибрати першу та третю купки: $x=4$ та $y=3$. Після того, як вона забере камінці, у купках буде $3,4,2$ камінців відповідно.

Боб повинен вибрати купки, у яких $x=4$ та $y=3$ камінці, тому він вибере другу та першу купки відповідно. Після того, як він забере камінці, у купках буде $2,3,2$ камінців відповідно.

Наступного кроку Аліса може вибрати, наприклад, другу та третю купки: $x=3$ та $y=2$. Після того, як вона забере камінці, у купках буде $2,2,1$ камінців відповідно.

Боб не зможе вибрати такі купки, щоб в них було $x=3$ та $y=2$ камінців, тому процес закінчується. Залишається $2+2+1=5$ камінців.

Оцінювання

1. ($17$ балів) $n\le 8$; $a_i\le 8$;

2. ($23$ балів) $n$ — парне; $a_1=a_2,a_3=a_4,\dots ,a_{n-1}=a_n$;

3. ($22$ балів) всі $a_i$ — парні;

4. ($18$ балів) $a_i\le 2\cdot 10^5$

5. ($20$ балів) без додаткових обмежень.