Conference
Sem and Yura are presenting at a conference, where they have a total of ( n ) presentations. The boredom level of the ( i )-th presentation is denoted as ( a_i ). The conference spans ( k ) days, and each presentation must be delivered exactly once by either Sem or Yura on one of these days.
Each day must feature at least one presentation by both Sem and Yura.
The boredom level for a day is determined by the XOR 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 XOR operation, represented as ⊕, is an addition operation modulo 2. To compute the XOR of two numbers ( a ) and ( b ), convert both numbers to binary and perform bitwise addition modulo 2. For example, ( 4 ) ⊕ ( 6 = 2 ), because ( 4_{10} = 100_2 ) and ( 6_{10} = 110_2 ). Thus, ( 4_{10} ) ⊕ ( 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 XOR of a set of numbers ( c[1], c[2], \ldots, c[k] ) is calculated as (...((( c[1] ) ⊕ ( c[2] )) ⊕ ( c[3] )) ... ⊕ ( c[k] )).
Input Format
The first line contains two integers ( n ) and ( k ) (( 1 \leq k \leq n \leq 10^5 )) — the number of presentations and the number of days.
The second line contains ( n ) integers ( a[1], a[2], \ldots, a[n] ) (( 1 \leq a[i] \leq 10^9 )) — the boredom level of each presentation.
Output Format
Output a single integer — the minimal total boredom level.