//std.cpp
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int n,m,a[maxn],sum[maxn],b[maxn],c;
int ans[maxn];
int s[maxn];

int tmp[maxn];


// range add, range min
int mn[maxn<<2],tag[maxn<<2];
void up(int p){
	mn[p]=min(mn[p<<1],mn[p<<1|1])+tag[p];
}
void build(int p,int l,int r,int*a){
	tag[p]=0;
	if(l==r)return mn[p]=a[l],void();
	int mid=l+r>>1;
	build(p<<1,l,mid,a),build(p<<1|1,mid+1,r,a),up(p);
}
void add(int p,int l,int r,int nl,int nr,int v){
	if(nl>nr)return;
	if(l>=nl&&r<=nr)return tag[p]+=v,mn[p]+=v,void();
	int mid=l+r>>1;
	if(nl<=mid)add(p<<1,l,mid,nl,nr,v);
	if(nr>mid)add(p<<1|1,mid+1,r,nl,nr,v);
	up(p);
}
int ask(int p,int l,int r,int ql,int qr){
	if(ql>qr)return 1e18;
	if(l>=ql&&r<=qr)return mn[p];
	int mid=l+r>>1,res=1e18;
	if(ql<=mid)res=min(res,ask(p<<1,l,mid,ql,qr));
	if(qr>mid)res=min(res,ask(p<<1|1,mid+1,r,ql,qr));
	return res+tag[p];
}

int qwq[maxn];
int id[maxn];

void work()
{
	n=read(),m=read(),c=read();
	int bb=m;
	For(i,1,n)a[i]=read(),sum[i]=sum[i-1]+a[i];
	For(i,1,n)b[i]=read();
	For(i,1,n){
		int t=min(min(b[i],a[i]%c),m);
		ans[i]=t;
		m-=t;
		m+=(a[i]-ans[i])/c;
	}
	s[0]=bb;
	For(i,1,n)s[i]=s[i-1]-ans[i]+(a[i]-ans[i])/c;
	int now=s[n];
	Rep(i,n,1){
//		cout<<"Now "<<now<<"\n";
		int tmp=min(b[i]-ans[i],s[i-1]-ans[i]);
		tmp/=c;
		tmp=min(tmp,now/(c+1));
		ans[i]+=c*tmp;
		now-=(c+1)*tmp;
		now=min(now,s[i-1]-ans[i]);
	}
	For(i,1,n)s[i]=s[i-1]-ans[i]+(a[i]-ans[i])/c;
	
	For(i,1,n)tmp[i]=s[i-1]-ans[i];
	tmp[n+1]=s[n];
	// del_i <= min(lim[i],lim[j(i<j<=n+1)]-1,b[i]-ans[i]).
	
	build(1,1,n+1,tmp);
	For(i,1,n)id[i]=i,qwq[i]=min(c-1,b[i]-ans[i]);
	sort(id+1,id+n+1,[&](int x,int y){
		return qwq[x]>qwq[y];
	});
	priority_queue<int>st;
	
	auto del=[&](int u,int d){
	//	cout<<"del "<<u<<" "<<d<<"\n";
		st.pop();
		ans[u]+=d;
		add(1,1,n+1,u,u,-d);
		add(1,1,n+1,u+1,n+1,-(d+1));
	};
	
	for(int l=1,r;l<=n;l=r+1){
		r=l;
		while(r<n && qwq[id[r+1]]==qwq[id[l]])++r;
		int dw=qwq[id[r+1]];
		if(r==n) dw=0;
		For(i,l,r)st.push(id[i]);
		while(st.size()){
			int u=st.top();
			int d=min(ask(1,1,n+1,u,u),ask(1,1,n+1,u+1,n+1)-1);
			d=min(d,qwq[u]);
			if(d>dw) del(u,d);
			else break;
		}
	}
	
//	now=s[n];
//	Rep(add,c-1,1){
//		For(i,1,n)s[i]=s[i-1]-ans[i]+(a[i]-ans[i])/c;
//		int now=s[n];
//		Rep(i,n,1){
//			if(add<=b[i]-ans[i] && add<=s[i-1]-ans[i]){
//				int cs=add+1;
//				if(now>=cs){
//					ans[i]+=add;
//					now-=cs;
//				}
//			}
//			now=min(now,s[i-1]-ans[i]);
//		}
//	}
	
	int out=0;
	For(i,1,n)out+=a[i]-ans[i];
	cout<<out<<"\n";
//	For(i,1,n)cout<<ans[i]<<" ";
}

signed main()
{
//	freopen("data.in","r",stdin);
//	freopen("now.out","w",stdout);
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/