#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int , int> pii;
typedef double db;
#define fi first
#define se second
#define rep(i , a , b) for(int i = a; i < b; i ++)
#define per(i , a , b) for(int i = a; i > b i --)
#define rrep(i , a , b , c) for(int i = a; i < b; i += c)
#define pper(i , a , b , c) for(int i = a; i > b; i -= c)
#define pb push_back
#define pob pop_back
#define sz(a) a.size()
#define be(a) a.begin()
#define ed(a) a.end()


void solve()
{
    vi item; // 创建一个数组来存Alice和Bob的item
    int t;
    scanf("%d" , &t); 
    while(t --)
    {
        int n , k , x;
        scanf("%d%d" , &n , &k);
        rep (i , 0 , n)
        {
            scanf("%d" , &x);
            item.pb(x); // 存储item
        }
        sort(be(item) , ed(item)); // 排序，因为Alice和Bob拿的item价值总是拿当前最多的
        int res = 0;
        pper (i , sz(item) - 1 , 0 , 2)
        {
            int delta = item[i] - item[i - 1]; // 算出Alice和Bob所拿item价值的差值
            int rdelta = min(delta , k); // 算出的差值和k比较出较小的
            item[i - 1] += rdelta; // 添加Bob的item
            k -= rdelta; 
            res += item[i] - item[i - 1]; // 算出之后的差值
        }

        if (sz(item) % 2 == 1) res += item[0]; // 如果总item数目是奇数个，那么最后一个物品一定是Alice所拿
        printf("%d\n" , res);
        while(sz(item)) item.pob(); // 每个样例输出结束后清空数组
    }
    return ;
}

int main()
{
    solve();
    // system("pause");
    return 0;
}