Пари камінців#259
У Аліси та Боба є купок з камінцями, пронумерованих від до . У -ій купці a_i камінців. Вони виконують наступний процес:
Аліса вибирає дві непусті купки. Нехай у них та камінців відповідно.
Аліса забирає по одному камінцю з цих купок.
Далі Боб теж вибирає дві непусті купки так, щоб у них також було та камінців відповідно. Тобто Боб вибирає дві купки так, щоб у них була така ж кількість камінців, як було початково у купках Аліси. Бобу дозволяється вибирати купки, які вибрала Аліса. Якщо він це зробити не може, то процес закінчується.
Боб також забирає по одному камінцю з вибраних ним купок.
Якщо кількість непорожніх купок менша за , то описаний процес закінчується, інакше знову повторюється спочатку.
Зверніть увагу, що Аліса не зобов'язана вибирати кожного разу одні й ті ж самі значення та .
Аліса і Боб хочуть зробити так, щоб у купках залишилось якнайменше камінців. Зауважте, що в них спільна мета. Допоможіть їм знайти мінімальну кількість камінців, які можуть залишитися.
Перший рядок містить два цілі числа та (2 \leq n \leq 2 \cdot 10^5, 0 \leq g \leq 5) — кількість купок та номер блока.
Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9) — кількість камінців у кожній купці.
Виведіть одне число — відповідь на задачу.
Приклад
Приклад 1
У першому прикладі Аліса може спочатку вибрати першу та третю купки: x=4 та y=3. Після того, як вона забере камінці, у купках буде камінців відповідно.
Боб повинен вибрати купки, у яких x=4 та y=3 камінці, тому він вибере другу та першу купки відповідно. Після того, як він забере камінці, у купках буде камінців відповідно.
Наступного кроку Аліса може вибрати, наприклад, другу та третю купки: x=3 та y=2. Після того, як вона забере камінці, у купках буде камінців відповідно.
Боб не зможе вибрати такі купки, щоб в них було x=3 та y=2 камінців, тому процес закінчується. Залишається 2+2+1=5 камінців.
( балів) n \le 8; a_i \le 8;
( балів) — парне; a_1=a_2,\ a_3=a_4,\ \dots,\ a_{n-1}=a_{n};
( балів) всі a_i — парні;
( балів) a_i \le 2 \cdot 10^5
( балів) без додаткових обмежень.