#include <bits/stdc++.h>

#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n';
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n';
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args);
#else
#define dbg(x) void();
#define dpi(x, y) void();
#define dbgf(fmt, args...) void();
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;

bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> T cmax(T &a, T b) { return a = max(a, b); }
template<typename T> T cmin(T &a, T b) { return a = min(a, b); }

namespace FastIO {
	constexpr int LEN = 1 << 20;
	char in[LEN + 1], out[LEN + 1];
	char *pin = in, *pout = out, *ein = in, *eout = out + LEN;

	char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
	void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
	void Flush() { fwrite(out, 1, pout - out, stdout); pout = out; }

	template<typename T> T Read() {
		T x = 0; int f = 1; char ch = gc();
		while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return x * f;
	}
	template<typename T> void Write(T x, char c) {
		static char stk[40]; int tp = 0;
		if (x < 0) pc('-'), x = ~x + 1;
		do stk[tp++] = x % 10 + 48, x /= 10; while (x);
		while (tp --) pc(stk[tp]); pc(c); return;
	}
	void Read(char *s) {
		char ch = gc();
		while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
			(ch >= '0' && ch <= '9'))) ch = gc();
		while ((ch != EOF) && ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
			(ch >= '0' && ch <= '9'))) *s = ch, s ++, ch = gc();
		*s = '\0'; return;
	}
	void Write(char *s) {
		while (*s != '\0') pc(*s), s ++; return;
	}
	void Puts(char *s) {
		Write(s), pc('\n'); return;
	}
}

#define getchar FastIO::gc
#define putchar FastIO::pc
#define Flush FastIO::Flush
#define Read FastIO::Read
#define Write FastIO::Write
#define Puts FastIO::Puts

constexpr int MAXN = 2e4 + 5, MAXV = 2e4 + 5;
int n, c, a[MAXN], mx;
int f[2][MAXV << 1];

int &F(int o, int i) { return f[o][i + mx]; }

void slv() {
	n = Read<int>(), c = Read<int>();
	for (int i = 1; i <= n; i ++)
		cmax(mx, a[i] = Read<int>());
	int pos = 0; int sum = 0;
	while (pos < n && sum + a[pos + 1] <= c)
		sum += a[++ pos];
	if (pos == n || sum == c) { Write(sum, '\n'); return; }
	int now = 0, nxt = 1;
	F(now, sum - c) = pos + 1;
//		cout << pos << ':' << endl;
//		for (int i = - mx + 1; i <= mx; i ++)
//			if (F(now, i)) cout << c + i << ' ' << F(now, i) << endl;
//		cout << endl;
	for (int r = pos; r < n; r ++) {
//		for (int i = mx; i < mx * 2; i ++) {
//			cmax(f[nxt][i], f[now][i]);
//			for (int l = f[now][i]; l < f[nxt][i]; l ++)
//				cmax(f[nxt][i - a[l]], l);
//		}
//		for (int i = 0; i < mx; i ++) {
//			cmax(f[nxt][i], f[now][i]);
//			cmax(f[nxt][i + a[r + 1]], f[now][i]);
//		}
		for (int i = - 1; i > - mx; i --) {
			cmax(F(nxt, i), F(now, i));
			cmax(F(nxt, i + a[r + 1]), F(now, i));
		}
		for (int i = mx - 1; i >= 0; i --) {
			cmax(F(nxt, i), F(now, i));
			for (int l = F(now, i); l < F(nxt, i); l ++)
				cmax(F(nxt, i - a[l]), l);
		}
		swap(now, nxt);
//		cout << r + 1 << ':' << endl;
//		for (int i = - mx + 1; i <= mx; i ++)
//			if (F(now, i)) cout << c + i << ' ' << F(now, i) << endl;
//		cout << endl;
	}
	int ans = 0;
	while (!F(now, ans)) ans --;
	Write(c + ans, '\n');
	return;
}
void clr() {
	for (int j = - mx + 1; j <= mx; j ++)
		for (int i : {0, 1}) F(i, j) = 0;
	mx = 0;
	return;
}

bool Med;
int main() {
#ifdef LOCAL
	freopen("!in.in", "r", stdin);
	freopen("!out.out", "w", stdout);
	fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
//	int T = 1;
	int T = Read<int>();
	while (T --) slv(), clr();
	Flush();
#ifdef LOCAL
	fprintf(stderr, "%d ms\n", (int)clock());
#endif
	return 0;
}