#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pb push_back
const int N=5e5+5;
int n,k,q[N],h,t;
char s[N];
ll f[N],g[N],a[N],c[N];
void init(ll* f){
	h=1,t=0;
	f[0]=0;
	q[++t]=0;
	for(int i=1;i<=n+1;i++){
		while(i-q[h]>k) h++;
		f[i]=f[q[h]]+a[i];
		if(s[i]=='1') h=1,t=0;
		while(h<=t&&f[q[t]]>=f[i]) t--;
		q[++t]=i;
	}
}
ll dp(int x,int y){
	int t=a[x];a[x]=y;
	ll ret=1e18;
	h=1,t=0;
	for(int i=k;i>0;i--) if(x-i>=0){
		if(s[x-i]=='1') h=1,t=0;
		while(h<=t&&q[t]>=f[x-i]) t--;
		q[++t]=x-i;c[x-i]=f[x-i];
	}
	for(int i=x;i<x+k&&i<=n+1;i++){
		while(q[h]<i-k) h++;
		c[i]=c[q[h]]+a[i];
		ret=min(ret,c[i]+g[i]);
		if(s[i]=='1') h=1,t=0;
		while(h<=t&&c[q[t]]>=c[i]) t--;
		q[++t]=i;
	}
	a[x]=t;
	return ret;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	a[n+1]=0;
	for(int i=1;i<=n;i++) cin>>s[i];
	init(f);
	reverse(a+1,a+n+1);reverse(s+1,s+n+1);
	init(g);reverse(a+1,a+n+1),reverse(s+1,s+n+1);
	reverse(g,g+n+2);
	for(int i=1;i<=n;i++) g[i]-=a[i];
	int q;cin>>q;
	while(q--){
		int x,y;cin>>x>>y;
		cout<<dp(x,y)<<'\n';
	}
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int t;cin>>t;
	while(t--)solve();
	return 0;
}