#include <bits/stdc++.h>
#define pb push_back
#define fastIO ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define all(v) v.begin(),v.end()
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef pair<long double,long double>pdd;
template<class T>
using max_pq = priority_queue<T>;
template<class T>
using min_pq = priority_queue<T,vector<T>,greater<T> >;
vector<string> split(const string& s, char c) {
vector<string> v; stringstream ss(s); string x;
while (getline(ss, x, c)) v.emplace_back(x); return move(v);
}
template<typename T, typename... Args>
inline string arrStr(T arr, int n) {
stringstream s; s << "[";
for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
if(n > 0)
s << arr[n - 1] ;
s<< "]";
return s.str();
}
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=20,MAXN=250000,INF=1e18;
int sz,h,arr1[N],arr2[N];
vector<int> t[4*MAXN];
vector<pii> v1,v2;
void brute(int day, int n, vector<pii> &v, int h1, int h2)
{
if(day==n+1)
{
v.pb({h1,h2});
return;
}
brute(day+1,n,v,h1+arr1[day],h2);
brute(day+1,n,v,h1,h2+arr2[day]);
brute(day+1,n,v,h1+arr1[day],h2+arr2[day]);
}
void build(vector<pii> a, int v, int tl, int tr) {
if (tl == tr) {
t[v] = vector<int>(1, a[tl].ss);
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
back_inserter(t[v]));
}
}
int query(int v, int tl, int tr, int l, int r, int x) {
if (l > r)
return 0;
if (l == tl && r == tr) {
auto pos = lower_bound(t[v].begin(), t[v].end(), x);
return (t[v].end()-pos);
}
int tm = (tl + tr) / 2;
return query(v*2, tl, tm, l, min(r, tm), x)+ query(v*2+1, tm+1, tr, max(l, tm+1), r, x);
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("debug.txt", "w", stderr);
#endif
fastIO;
int testcases;cin>>testcases;
for(int test=1;test<=testcases;test++)
{
cin>>sz>>h;
memset(t,0,sizeof(t));
for(int i=1;i<=sz;i++)
{
cin>>arr1[i];
}
for(int i=1;i<=sz;i++)
{
cin>>arr2[i];
}
int n=sz/2;
int m=sz-n;
v1.clear();v2.clear();
brute(1,n,v1,0,0);
brute(n+1,sz,v2,0,0);
sort(all(v2));
build(v2,1,0,v2.size()-1);
int ans=0;
for(int i=0;i<v1.size();i++)
{
int r=v2.size()-1;
auto it=lower_bound(all(v2),pii(h-v1[i].ff,0));
int l=(it-v2.begin());
int tmp=query(1,0,v2.size()-1,l,r,h-v1[i].ss);
if(tmp!=INF)
{
ans+=tmp;
}
}
cout<<"Case #"<<test<<": "<<ans<<endl;
}
return 0;
}
ICAgIAojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBwYiAgICAgIHB1c2hfYmFjawojZGVmaW5lIGZhc3RJTyAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKE5VTEwpO2NvdXQudGllKE5VTEwpOwojZGVmaW5lIFBJICAgICAgMy4xNDE1OTI2NTM1ODk3OTMyMzg0NjI2NDMzODMKI2RlZmluZSBtcCAgICAgIG1ha2VfcGFpcgojZGVmaW5lIGZmICAgICAgZmlyc3QKI2RlZmluZSBzcyAgICAgIHNlY29uZAojZGVmaW5lIGVuZGwgICAgIlxuIgojZGVmaW5lIGFsbCh2KSAgdi5iZWdpbigpLHYuZW5kKCkKI2RlZmluZSBpbnQgICAgIGxvbmcgbG9uZwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxvbmcgZG91YmxlLGxvbmcgZG91YmxlPnBkZDsKdGVtcGxhdGU8Y2xhc3MgVD4KdXNpbmcgbWF4X3BxID0gcHJpb3JpdHlfcXVldWU8VD47CnRlbXBsYXRlPGNsYXNzIFQ+CnVzaW5nIG1pbl9wcSA9IHByaW9yaXR5X3F1ZXVlPFQsdmVjdG9yPFQ+LGdyZWF0ZXI8VD4gPjsKCnZlY3RvcjxzdHJpbmc+IHNwbGl0KGNvbnN0IHN0cmluZyYgcywgY2hhciBjKSB7CiAgICB2ZWN0b3I8c3RyaW5nPiB2OyBzdHJpbmdzdHJlYW0gc3Mocyk7IHN0cmluZyB4OwogICAgd2hpbGUgKGdldGxpbmUoc3MsIHgsIGMpKSB2LmVtcGxhY2VfYmFjayh4KTsgcmV0dXJuIG1vdmUodik7Cn0KdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUuLi4gQXJncz4KaW5saW5lIHN0cmluZyBhcnJTdHIoVCBhcnIsIGludCBuKSB7CiAgICBzdHJpbmdzdHJlYW0gczsgcyA8PCAiWyI7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbiAtIDE7IGkrKykgcyA8PCBhcnJbaV0gPDwgIiwiOwogICAgICAgIGlmKG4gPiAwKQogICAgICAgICAgICBzIDw8IGFycltuIC0gMV0gOwogICAgICAgIHM8PCAiXSI7CiAgICAgICAgcmV0dXJuIHMuc3RyKCk7CiAgICB9CiNkZWZpbmUgVFJBQ0UKI2lmZGVmIFRSQUNFCiNkZWZpbmUgdHJhY2UoLi4uKSBfX2YoI19fVkFfQVJHU19fLCBfX1ZBX0FSR1NfXykKICAgIHRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxPgogICAgdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZSwgQXJnMSYmIGFyZzEpewogICAgICAgIGNlcnIgPDwgbmFtZSA8PCAiIDogIiA8PCBhcmcxIDw8IGVuZGw7CiAgICB9CiAgICB0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMSwgdHlwZW5hbWUuLi4gQXJncz4KICAgIHZvaWQgX19mKGNvbnN0IGNoYXIqIG5hbWVzLCBBcmcxJiYgYXJnMSwgQXJncyYmLi4uIGFyZ3MpewogICAgICAgIGNvbnN0IGNoYXIqIGNvbW1hID0gc3RyY2hyKG5hbWVzICsgMSwgJywnKTsgY2Vyci53cml0ZShuYW1lcywgY29tbWEgLSBuYW1lcykgPDwgIiA6ICIgPDwgYXJnMTw8IiB8ICI7X19mKGNvbW1hKzEsIGFyZ3MuLi4pOwogICAgfQojZWxzZQojZGVmaW5lIHRyYWNlKC4uLikKI2VuZGlmCmNvbnN0IGludCBOPTIwLE1BWE49MjUwMDAwLElORj0xZTE4OwoKaW50IHN6LGgsYXJyMVtOXSxhcnIyW05dOwp2ZWN0b3I8aW50PiB0WzQqTUFYTl07CnZlY3RvcjxwaWk+IHYxLHYyOwoKdm9pZCBicnV0ZShpbnQgZGF5LCBpbnQgbiwgdmVjdG9yPHBpaT4gJnYsIGludCBoMSwgaW50IGgyKQp7CiAgICBpZihkYXk9PW4rMSkKICAgIHsKICAgICAgICB2LnBiKHtoMSxoMn0pOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGJydXRlKGRheSsxLG4sdixoMSthcnIxW2RheV0saDIpOwogICAgYnJ1dGUoZGF5KzEsbix2LGgxLGgyK2FycjJbZGF5XSk7CiAgICBicnV0ZShkYXkrMSxuLHYsaDErYXJyMVtkYXldLGgyK2FycjJbZGF5XSk7Cn0KCgp2b2lkIGJ1aWxkKHZlY3RvcjxwaWk+IGEsIGludCB2LCBpbnQgdGwsIGludCB0cikgewogICAgaWYgKHRsID09IHRyKSB7CiAgICAgICAgdFt2XSA9IHZlY3RvcjxpbnQ+KDEsIGFbdGxdLnNzKTsKICAgIH0gZWxzZSB7IAogICAgICAgIGludCB0bSA9ICh0bCArIHRyKSAvIDI7CiAgICAgICAgYnVpbGQoYSwgdioyLCB0bCwgdG0pOwogICAgICAgIGJ1aWxkKGEsIHYqMisxLCB0bSsxLCB0cik7CiAgICAgICAgbWVyZ2UodFt2KjJdLmJlZ2luKCksIHRbdioyXS5lbmQoKSwgdFt2KjIrMV0uYmVnaW4oKSwgdFt2KjIrMV0uZW5kKCksCiAgICAgICAgICAgICAgYmFja19pbnNlcnRlcih0W3ZdKSk7CiAgICB9Cn0KCmludCBxdWVyeShpbnQgdiwgaW50IHRsLCBpbnQgdHIsIGludCBsLCBpbnQgciwgaW50IHgpIHsKICAgIGlmIChsID4gcikKICAgICAgICByZXR1cm4gMDsKICAgIGlmIChsID09IHRsICYmIHIgPT0gdHIpIHsKICAgICAgICBhdXRvIHBvcyA9IGxvd2VyX2JvdW5kKHRbdl0uYmVnaW4oKSwgdFt2XS5lbmQoKSwgeCk7CiAgICAgICAgcmV0dXJuICh0W3ZdLmVuZCgpLXBvcyk7CiAgICB9CiAgICBpbnQgdG0gPSAodGwgKyB0cikgLyAyOwogICAgcmV0dXJuIHF1ZXJ5KHYqMiwgdGwsIHRtLCBsLCBtaW4ociwgdG0pLCB4KSsgcXVlcnkodioyKzEsIHRtKzEsIHRyLCBtYXgobCwgdG0rMSksIHIsIHgpOwp9CgppbnQzMl90IG1haW4oKQp7CiAgICAjaWZuZGVmIE9OTElORV9KVURHRQogICAgZnJlb3BlbigiaW5wdXQudHh0IiwgInIiLCBzdGRpbik7CiAgICBmcmVvcGVuKCJvdXRwdXQudHh0IiwgInciLCBzdGRvdXQpOwogICAgZnJlb3BlbigiZGVidWcudHh0IiwgInciLCBzdGRlcnIpOwogICAgI2VuZGlmCgogICAgZmFzdElPOwoKICAgIGludCB0ZXN0Y2FzZXM7Y2luPj50ZXN0Y2FzZXM7CiAgICBmb3IoaW50IHRlc3Q9MTt0ZXN0PD10ZXN0Y2FzZXM7dGVzdCsrKQogICAgewogICAgICAgIGNpbj4+c3o+Pmg7CiAgICAgICAgbWVtc2V0KHQsMCxzaXplb2YodCkpOwogICAgICAgIGZvcihpbnQgaT0xO2k8PXN6O2krKykKICAgICAgICB7CiAgICAgICAgICAgIGNpbj4+YXJyMVtpXTsKICAgICAgICB9CiAgICAgICAgZm9yKGludCBpPTE7aTw9c3o7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5hcnIyW2ldOwogICAgICAgIH0KICAgICAgICBpbnQgbj1zei8yOwogICAgICAgIGludCBtPXN6LW47CiAgICAgICAgdjEuY2xlYXIoKTt2Mi5jbGVhcigpOwogICAgICAgIGJydXRlKDEsbix2MSwwLDApOwogICAgICAgIGJydXRlKG4rMSxzeix2MiwwLDApOwogICAgICAgIHNvcnQoYWxsKHYyKSk7CiAgICAgICAgYnVpbGQodjIsMSwwLHYyLnNpemUoKS0xKTsKICAgICAgICBpbnQgYW5zPTA7CiAgICAgICAgZm9yKGludCBpPTA7aTx2MS5zaXplKCk7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHI9djIuc2l6ZSgpLTE7CiAgICAgICAgICAgIGF1dG8gaXQ9bG93ZXJfYm91bmQoYWxsKHYyKSxwaWkoaC12MVtpXS5mZiwwKSk7CiAgICAgICAgICAgIGludCBsPShpdC12Mi5iZWdpbigpKTsKICAgICAgICAgICAgaW50IHRtcD1xdWVyeSgxLDAsdjIuc2l6ZSgpLTEsbCxyLGgtdjFbaV0uc3MpOwogICAgICAgICAgICBpZih0bXAhPUlORikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYW5zKz10bXA7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dDw8IkNhc2UgIyI8PHRlc3Q8PCI6ICI8PGFuczw8ZW5kbDsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0K