#include <bits/stdc++.h>
using namespace std;
#define maxn 500010

#define cn getchar
template<class TY>void read(TY &x){
	x=0;int f1=1;char ch=cn();
	while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
	if(x>9)write2(x/10);
	putchar(x%10+'0');
}
template<class TY>void write(TY x){
	if(x<0)putchar('-'),x=-x;
	write2(x);
}
int n,k,q,a[maxn];
char s[maxn];
struct node{
	int l,r,mid;
	long long mi;
	node *zuo,*you;
	node(int x,int y):l(x),r(y),mid(l+r>>1),mi(1e18),zuo(NULL),you(NULL){
		if(l==r)return;
		zuo=new node(l,mid);
		you=new node(mid+1,r);
	}
	void change(int x,long long z){
		if(l==r){
			mi=z;
			return;
		}
		if(x<=mid)zuo->change(x,z);
		else you->change(x,z);
		mi=min(zuo->mi,you->mi);
	}
	long long query(int x,int y){
		if(l==x&&r==y)return mi;
		if(y<=mid)return zuo->query(x,y);
		else if(x>mid)return you->query(x,y);
		else return min(zuo->query(x,mid),you->query(mid+1,y));
	}
}*rt[2];
int le[maxn],ri[maxn];
long long st0[maxn][20],st1[maxn][20];
int log_2[maxn];

int main()
{
	for(int i=2;i<=maxn-10;i++)
		log_2[i]=log_2[i>>1]+1;
	int Te;read(Te);while(Te--){
		read(n);read(k);
		for(int i=1;i<=n;i++)
			read(a[i]); a[n+1]=0;
		char ch=getchar(); n=0;
		while(ch<'0'||ch>'1')ch=getchar();
		while(ch>='0' && ch<='1')s[++n]=ch, ch=getchar();
		le[0]=0; rt[0]=new node(0,n+1);
		rt[0]->change(0,0);
		for(int i=1;i<=n+1;i++){
			if(s[i]=='1')le[i]=i;
			else le[i]=le[i-1];
			long long p=a[i] + rt[0]->query(max(le[i-1],i-k),i-1);
			rt[0]->change(i,p);
		}
		ri[n+1]=n+1; rt[1]=new node(0,n+1);
		rt[1]->change(n+1,0);
		for(int i=n;i>=0;i--){
			if(s[i]=='1')ri[i]=i;
			else ri[i]=ri[i+1];
			long long p=a[i] + rt[1]->query(i+1,min(i+k,ri[i+1]));
			rt[1]->change(i,p);
		}
		
		for(int i=0;i<=n+1;i++)
			st0[i][0]=rt[0]->query(i,i);
		for(int j=1;j<20;j++)if((1<<j)<=n)
			for(int i=1;i<=n-(1<<j)+1;i++)
				st0[i][j]=min(st0[i][j-1],st0[i+(1<<j-1)][j-1]);
		for(int i=0;i<=n+1;i++)
			st1[i][0]=rt[1]->query(i,i);
		for(int j=1;j<20;j++)if((1<<j)<=n)
			for(int i=1;i<=n-(1<<j)+1;i++)
				st1[i][j]=min(st1[i][j-1],st1[i+(1<<j-1)][j-1]);
		auto query0=[&](int x,int y){
			int lg = log_2[y-x+1];
			return min(st0[x][lg],st0[y-(1<<lg)+1][lg]);
		};
		auto query1=[&](int x,int y){
			int lg = log_2[y-x+1];
			return min(st1[x][lg],st1[y-(1<<lg)+1][lg]);
		};
		
		long long Cans = query0(n+1,n+1);
		read(q);
		for(int i=1;i<=q;i++){
			int x,y;read(x);read(y);
			if(s[x]=='1')write(Cans + y-a[x]),puts("");
			else{
				long long ans=0;
				ans += query0(max(x-k,le[x]),x-1) + query1(x+1,min(x+k,ri[x])) + y;
				for(int j=max(le[x],x-k+1);j<x;j++){
					ans = min(ans, query0(j,j) + query1(x+1,min(j+k,ri[x])));
					// printf("%d : %lld\n",j,rt[0]->query(j,j) + rt[1]->query(x+1,min(j+k,ri[x])));
				}
				write(ans);puts("");
			}
		}
	}
}
/*
1
10 3
5 10 7 100 4 3 12 5 100 1
0001000010
1
6 15
*/