#include<bits/stdc++.h>
#define ll long long
const ll INF=1e18;
using namespace std;
const int N=1e6+5;
int n,m,a[N],q[N];
ll f[N],g[N],h[N];
char s[N];
int main() {
	freopen("1.in","r",stdin);
	int T; scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
		} 
		a[n+1]=0;
		scanf("%s",s+1);
		int l=1,r=1; q[1]=0; f[0]=0;
		for(int i=1;i<=n+1;++i) {
			while(l<=r&&q[l]<i-m) ++l;
			f[i]=f[q[l]]+a[i];
			if(s[i]=='1') {
				r=l; q[r]=i;
			} else {
				while(l<=r&&f[q[r]]>=f[i]) --r;
				q[++r]=i;
			}
		}
		l=1,r=1; q[1]=n+1; g[n+1]=0;
		for(int i=n;i>=0;--i) {
			while(l<=r&&q[l]>i+m) ++l;
			g[i]=g[q[l]]+a[i];
			if(s[i]=='1') {
				r=l; q[r]=i;
			} else {
				while(l<=r&&g[q[r]]>=g[i]) --r;
				q[++r]=i;
			}
		}
/*		for(int i=1;i<=n+1;++i) {
			cerr<<f[i]<<' ';
		}
		cerr<<'\n';
		for(int i=0;i<=n;++i) {
			cerr<<g[i]<<' ';
		}
		cerr<<'\n';
*/		
		int Q; scanf("%d",&Q);
		while(Q--) {
			int x,y; scanf("%d%d",&x,&y);
			if(s[x]=='1') {
				printf("%lld\n",f[n+1]-a[x]+y);
				continue;
			}
			ll s1=INF,s2=INF;
			for(int i=x-1;i>=max(0,x-m);--i) {
				if(s[i]=='0') s1=min(s1,f[i]);
					else {
						s1=f[i]; break;
					}
			}
			for(int i=x+1;i<=min(n+1,x+m);++i) {
				if(s[i]=='0') {
					s2=min(s2,g[i]);
				} else {
					s2=g[i]; 
					break;
				}
			}
			ll ans=s1+s2+y;
			h[x]=INF;
			for(int i=x+1;i<=min(n+1,x+m-1);++i) {
				h[i]=min(h[i-1],g[i]);
				if(s[i]=='1') {
					for(int j=i+1;j<=min(n+1,x+m-1);++j) {
						h[j]=h[i];
					}
					break;
				}
			}
			for(int i=x-1;i>=max(0,x-m+1);--i) {
				ans=min(ans,f[i]+h[min(n+1,i+m)]);
				if(s[i]=='1') break;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}