背景

试题来自 清华大学学生算法协会。

题目描述

NIT 喜欢圆形的螺丝。他也喜欢 $\oplus$ 运算符，因为它让他想起圆形的螺丝。这里 $\oplus$ 表示按位异或运算。

定义一个序列 $a_1, a_2, \cdots, a_n$ 的价值 $V_a$ 为 $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$。

给定一个序列 $a_1, a_2, \cdots, a_n$，你可以执行任意次如下操作：

• 选择一个下标 $i$ ($1 \le i \le n$)，将 $a_i$ 改为任意非负整数；该操作的花费为 $C$。

请最小化序列的价值与操作花费之和。换言之，设 $p$ 为你执行的操作次数，$V_{a'}$ 为操作后序列 $a$ 的价值，你需要最小化 $pC + V_{a'}$。

输入格式

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每组测试用例，第一行包含两个整数 $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$)，分别表示序列长度和一次操作的花费。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$)，表示序列中的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例，输出一行一个整数，即 $pC + V_{a'}$ 可能的最小值。

3
4 4
1 4 5 6
8 6
6 6 6 1 1 6 6 6
6 7
1 7 2 6 3 5

14
24
29

提示

对于第 $1$ 组测试用例，一种达到最小值的方式是将序列变为 $[1, \textbf{1}, \textbf{1}, \textbf{0}]$；加粗的数字是被修改过的。最终序列的价值为 $2$，共执行了 $3$ 次操作；总价值 $+$ 花费为 $2 + 3 \times 4 = 14$。

对于第 $2$ 组测试用例，一种达到最小值的方式是将序列变为 $[6, 6, 6, \textbf{6}, \textbf{6}, 6, 6, 6]$；最终价值为 $12 + 2 \times 6 = 24$。

翻译由 DeepSeek V4 Pro 完成