题目描述

给出一个长度为 $n$ 的数列 $a$。

一个数列的权值定义为 $a_1+a_n+a_1 \oplus a_2 + a_2 \oplus a_3 +… + a_{n-1} \oplus a_n$。

你可以花费 $C$​ 的代价将数列中的某一个数修改成任意值。

假设你修改了 $k$ 次，修改后的数列 $a’$ 的权值为 $V$，你需要最小化并输出 $V+Ck$ 的权值。

输入格式

第一行给出两个正整数 $n,C$​。

第二行给出 $n$ 个数，表示 $a_1,a_2,…,a_n$。

输出格式

输出一个整数，表示答案。

4 4
1 4 5 6

14

8 6
6 6 6 1 1 6 6 6

24

6 7
1 7 2 6 3 5

29

详见下发文件。

详见下发文件。

详见下发文件。

详见下发文件。

详见下发文件。

详见下发文件。

说明提示

数据范围

对于 $30\%$ 的数据，$2\leq n\leq5000$

对于另外 $30\%$ 的数据，$0\leq a_i<2^9$

对于 $100\%$ 的数据，$2\leq n\leq10^5,0\leq a_i,C<2^{18}$