Conference#8771
Sem and Yura are presenting at a conference, where they have a total of presentations. The boredom level of the -th presentation is denoted as a_i. The conference spans days, and each presentation must be delivered exactly once by either Sem or Yura on one of these days.
Each day must have at least one presentation.
The boredom level for a day is determined by the of the boredom levels of all presentations given on that day. The conference organizers aim to schedule the presentations in a way that minimizes the sum of the boredom levels across all days.
The operation, represented as , is an addition operation modulo 2. To compute the of two numbers and , convert both numbers to binary and perform bitwise addition modulo 2. For example, 4 \oplus 6 = 2, because 4_{10} = 100_2 and 6_{10} = 110_2. Thus, 4_{10} \oplus 6_{10} = 010_2 = 2_{10}.
In programming languages like C++, C#, and Java, this operation is implemented as the operator **^**, and in Pascal, it is **xor**. The of a set of numbers c_1, c_2, \ldots, c_k is calculated as (...((c_1 \oplus c_2) \oplus c_3) ... \oplus c_k).
The first line contains two integers and (1 \leq k \leq n \leq 10^5) — the number of presentations and the number of days.
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the boredom level of each presentation.
Output a single integer — the minimal total boredom level.
Example 1