#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int M=5e5+5;
int n,m,k,p,v;char s[M];
int a[M],q[M];LL f[M],F[M],g[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
void solve(){
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	scanf("%s",s+1);a[++n]=0;s[0]=s[n]='0';
	int head=0,tail=0;q[0]=0;
	for (int i=1;i<=n;i++){
		while (head<tail&&i-q[head]>m) head++;
		f[i]=f[q[head]]+a[i];
		if (s[i]^48) head=1,tail=0;
		while (head<tail&&f[q[tail]]>=f[i]) tail--;
		q[++tail]=i;
	} g[n]=0; q[head=tail=0]=n;
	for (int i=n-1;i;i--){
		while (head<tail&&q[head]-i>m) head++;
		g[i]=g[q[head]]+a[i];
		if (s[i]^48) head=1,tail=0;
		while (head<tail&&g[q[tail]]>=g[i]) tail--;
		q[++tail]=i;	
	}
	for (int i=1;i<=n;i++) F[i]=f[i];
	k=read();while (k--){
		p=read();v=read();LL ans=1ll<<60;
		swap(a[p],v);head=tail=0;
		for (int i=max(p-m,0);i<p;i++){
			while (head<tail&&i-q[head]>m) head++;
			if (s[i]^48) head=1,tail=0;
			while (head<tail&&f[q[tail]]>=f[i]) tail--;	
			q[++tail]=i;
		}
		for (int i=p;i<=min(p+m,n);i++){
			while (head<tail&&i-q[head]>m) head++;
			f[i]=f[q[head]]+a[i];
			if (s[i]^48) head=1,tail=0;
			while (head<tail&&f[q[tail]]>=f[i]) tail--;
			q[++tail]=i;
			if (i^p) ans=min(ans,f[i]+g[i]-a[i]);
		}
		for (int i=p;i<=min(p+m,n);i++) f[i]=F[i];
		printf("%lld\n",ans); swap(a[p],v);
	}
}
int main(){int T=read();
	while (T--) solve();
	return 0;
}