#include<cstdio>
#include<iostream>
using namespace std;
const int o=5e5+10;
int T,n,K,Q,a[o],q[o],hd,tl;long long f[o],g[o],ans;char s[o];
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&K);g[n+1]=0;
		for(int i=1;i<=n;++i) scanf("%d",&a[i]);
		scanf("%s",s+1);s[0]=s[n+1]=1;
		for(int i=1;i<=n;++i) s[i]-=48;
		q[hd=tl=1]=0;
		for(int i=1;i<=n;q[++tl]=i++){
			for(;hd<=tl&&i-q[hd]>K;++hd);
			f[i]=f[q[hd]]+a[i];
			if(s[i]) hd=1,tl=0;
			for(;hd<=tl&&f[i]<f[q[tl]];--tl);
		}
		q[hd=tl=1]=n+1;
		for(int i=n;i;q[++tl]=i--){
			for(;hd<=tl&&q[hd]-i>K;++hd);
			g[i]=g[q[hd]]+a[i];
			if(s[i]) hd=1,tl=0;
			for(;hd<=tl&&g[i]<g[q[tl]];--tl);
		}
		scanf("%d",&Q);
		for(int p,v,l,r;Q--;printf("%lld\n",ans)){
			scanf("%d%d",&p,&v);ans=f[p]+g[p]-2*a[p]+v;
			if(!s[p]&&K>1){
				long long val=g[r=p+1];
				for(l=p-1;l>p-K+1&&!s[l];--l);
				for(;l<p;ans=min(ans,f[l++]+val)) for(;r-l<K&&!s[r];val=min(val,g[++r]));
			}
		}
	}
	return 0;
}