eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Конференцiя

Конференцiя

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Сем i Юра виступають на конференцiї. Всього у них є n доповiдей, зануднiсть i-ої з яких рiвна ai. Конференцiя триває k днiв. Кожну доповiдь Сем i Юра читають рiвно один раз в один iз днiв.Кожного дня повинна бути принаймнi одна доповiдь Сема та Юри.

Зануднiсть дня рiвна xor занудностей всiх доповiдей, прочитаних в цей день. Органiзатори конференцiї хочуть так розставити доповiдi Сема та Юри, щоб мiнiмiзувати суму занудностей днiв.

Допоможiть їм в цьому.

Операцiя xor (позначається як ⊕) — операцiя додавання за модулем 2. Для того, щоб знайтиxor двох чисел a та b, потрiбно розкласти обидва числа у двiйкову систему та додати по модулю 2окремо кожен бiт. Наприклад, 46 = 2, бо 4[10] = 100[2], 6[10] = 110[2]. 4[10]6[10] = 010[2] = 2[10].

Дана операцiя реалiзована, як оператор ^ в C++, C#, Java та xor у Pascal. Хor набору чисел c[1]; c[2]; : : : ; c[k] рiвний (: : : ((c[1]c[2]) ⊕ c[3]) : : : ⊕ c[k]).

Вхідні дані

Перший рядок мiстить два цiлi числа n та k (1 ⩽ k ⩽ n ⩽ 10^5) — кiлькiсть доповiдей та кiлькiсть днiв.

Другий рядок мiстить n цiлих чисел a[1]; a[2]; : : : ; a[n] (1 ⩽ a[i]10^9) — зануднiсть i-ої доповiдi.

Вихідні дані

Виведiть єдине цiле число — мiнiмальну сумарну зануднiсть.

Приклад

Вхідні дані #1
7 4
47 74 4 7 7 4 7
Вихідні дані #1
106
Джерело 2019-2020 ACM-ICPC, SEERC, 1/8 фiналу, 13 квiтня 2019 року