解题思路

题目要求最终满足：

$

题目内容

$TK$有一个长度为$n$的数组{$a_1,a_2,...,a_n$}。$TK$总共可以执行以下两种操作，其中第一种操作最多可执行一次，第二种操作也最多可执行一次（两种操作可以组合使用）：

• 选择两个不同的下标$i,j$，将$a_i$修改为$a_i+a_j$，花费$k$的代价;

• 选择一个元素$a_i$以及任意正整数$x$，对其增加或减少$x$，花费$x$的代价。

$TK$希望花费最小的代价，使得

$a_1×a_2×...×a_n=0$

请输出这个最小代价。

输入描述

每个测试文件均包含多组测试数据

• 第一行输入一个整数$T(1≤T≤50)$,表示数据组数;

• 每组测试数据描述如下:

​ 1.在一行上输入两个整数$n,k（1≤n≤3000;1≤k≤10^9)$;

​ 2.在一行上输入$n$个整数$a_1,a_2,...,a_n（-10^9≤a_i≤10^9)$;

除此之外，保证单个测试文件中所有$n$的和不超过$3000$

输出描述

于每组测试数据，新起一行输出一个整数，表示最小花费代价

样例1

输入

2
3 5
1 -2 3
4 10
0 0 0 -5

输出

1
0

说明

• 对于第一组测试数据只需要将$a_1$减一即可