CF2004C Splitting Items

Alice 和 Bob 有 $n$ 个数，第 $i$ 个数为 $a_i$，他们决定玩一个游戏取走这些数。 游戏由 Alice 开始取数。 每一次玩家都可以拿走一个剩下的数，直到没有数字可拿走。 定义 $A$ 是 Alice 获取的数字和，$B$ 是 Bob 获取的数字和，游戏总分 $p = A - B$。 Alice 希望最大化 $p$，Bob 希望最小化 $p$，他们都绝顶聪明。 现在 Bob 拥有了修改数的权限，可以把一些数字（可以没有，也可以没有全部）**增加**一个整数值（可以增加不同的值），但是这样 Alice 可能会起疑心，所以总增加的数值必须小于等于 $k$。 请求出 Bob 能达到的 $p$ 的最小值。

**本题有多组数据。** 首先输入一个整数 $t (1 \le t \le 5000)$，表示数据组数。 对于每一组数据，第一行输入两个整数 $n, k (2 \le n \le 2 \times 10 ^ 5, 0 \le k \le 10 ^ 9)$，含义如题意描述。 注意到所有数据的 $n$ 总和不大于 $2 \times 10 ^ 5$。 下一行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n (1 \le a_i \le 10 ^ 9)$，表示每个数的值。

对于每组数据输出一个整数表示答案。

In the first test case, Bob can increase $ a_1 $ by $ 5 $ , making costs equal to $ [6, 10] $ . Tomorrow, Alice will take $ 10 $ and Bob will take $ 6 $ . The total score will be equal to $ 10 - 6 = 4 $ , and it's the minimum possible. In the second test case, Bob can't change costs. So the score will be equal to $ (15 + 10) - 12 = 13 $ , since Alice will take $ 15 $ , Bob will take $ 12 $ , and Alice — $ 10 $ . In the third test case, Bob, for example, can increase $ a_1 $ by $ 1 $ , $ a_2 $ by $ 3 $ , and $ a_3 $ by $ 2 $ . The total change is equal to $ 1 + 3 + 2 \le 6 $ and costs will be equal to $ [4, 4, 4, 4] $ . Obviously, the score will be equal to $ (4 + 4) - (4 + 4) = 0 $ . In the fourth test case, Bob can increase $ a_1 $ by $ 3 $ , making costs equal to $ [9, 9] $ . The score will be equal to $ 9 - 9 = 0 $ .