题目内容

你有一个长度为 $n$ 的整数序列 $s_1, s_2, \dots, s_n$。你可以执行以下两类操作，每类操作至多执行一次（可以都不执行，也可以只执行其中一类，或者两类都执行）：

• 合并操作：选择两个不同的下标 $i, j$，将 $s_i$ 替换为 $s_i + s_j$，代价为常数 $c$。
• 调整操作：选择一个元素 $s_i$ 以及一个正整数 $x$，将其增加或减少 $x$（即 $s_i \leftarrow s_i \pm x$），代价为 $x$。

你的目标是使得序列所有元素的乘积等于 $0$，即 $\prod_{i=1}^n s_i = 0$。请你计算达成目标所需的最小总代价。

约束条件

• 测试用例的数量 $T$ 满足 $1 \le T \le 50$。
• 序列长度 $n$ 满足 $1 \le n \le 3000$，且所有测试用例的 $n$ 之和不超过 $3000$。
• 合并操作的代价 $c$ 满足 $1 \le c \le 10^9$。
• 序列中每个整数 $s_i$ 的绝对值不超过 $10^9$（即 $-10^9 \le s_i \le 10^9$）。

输入描述

第一行包含一个整数 $T$，表示测试用例的数量。

接下来依次描述每个测试用例，每个测试用例包含两行：

• 第一行包含两个整数 $n$ 和 $c$，分别表示序列长度以及合并操作的代价。
• 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，表示初始序列。

输出描述

对于每个测试用例，输出一行一个整数，表示达成目标所需的最小总代价。

样例1

输入

1
2 3
10 -8

输出

5

说明

直接调整：将 10 变为 0 代价 10，或将 -8 变为 0 代价 8，较小代价为 8。 考虑先合并再调整：选择 10 和 -8 合并，得到 $10 + (-8) = 2$，合并代价 $c=3$，再将该结果调整为 0 代价 $|2|=2$，总代价 $3+2=5$。 比较两种方案，最小总代价为 5。

样例2

输入

2
4 5
2 3 -5 8
1 1
-1

输出

2
1

说明

第一个测试用例：直接调整的最小代价为 $\min(|2|,|3|,|-5|,|8|) = 2$（将 2 变为 0）。合并方案中，最小的 $|s_i + s_j|$ 为 $|3 + (-5)| = 2$，总代价为合并代价 5 加上调整代价 2，等于 7，高于直接调整的 2。因此该用例输出 2。 第二个测试用例：序列长度 $n=1$，无法执行合并操作（需要两个不同下标），只能通过调整将 $-1$ 变为 0，代价 $|-1| = 1$。因此输出 1。

样例3

输入

1
3 100
5 0 -3

输出

0

说明

序列中已经存在元素 0，因此所有元素的乘积已经为 $0$，不需要执行任何操作即可满足要求，总代价为 0。