#include<bits/stdc++.h> 
#define int long long 
#define x first 
#define y second 
#define il inline 
#define em emplace 
#define eb emplace_back 
#define debug() puts("-----") 
using namespace std; 
typedef pair<int,int> pii; 
il int read(){ 
	int x=0,f=1; char ch=getchar(); 
	while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } 
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 
	return x*f; 
} 
const int N=5e5+10; 
int n,k; 
int a[N]; 
bool st[N]; 
int f[N],g[N]; 
int q[N],hh,tt; 
il void solve(){ 
	n=read(),k=read(); int sum=0; 
	for(int i=1;i<=n;i++) a[i]=read(); 
	for(int i=1;i<=n;i++){ 
		char c; cin>>c; 
		if(c=='1') st[i]=true,sum+=a[i]; 
		else st[i]=false; 
	} f[0]=g[n+1]=0; 
	hh=tt=0,q[0]=0; 
	for(int i=1;i<=n;i++){ 
		while(hh<=tt&&i-q[hh]>k) hh++; 
		int val=a[i]; 
		if(st[i]) val=0; 
		f[i]=f[q[hh]]+val; 
		while(hh<=tt&&f[q[tt]]>=f[i]) tt--; 
		q[++tt]=i; 
	} hh=tt=0,q[0]=n+1; 
	for(int i=n;i>=1;i--){ 
		while(hh<=tt&&q[hh]-i>k) hh++; 
		int val=a[i]; 
		if(st[i]) val=0; 
		g[i]=g[q[hh]]+val; 
		while(hh<=tt&&g[q[tt]]>=g[i]) tt--; 
		q[++tt]=i; 
	} int Q=read(); 
	while(Q--){ 
		int x=read(),v=read(); 
		if(st[x]) sum-=a[x],sum+=v; 
		int L=max(0ll,x-k),R=min(n+1,x+k); 
		int ans=1e18,val=v; 
		if(st[x]) val=0; 
		int Min=1e18; 
		for(int i=L;i<x;i++) Min=min(Min,f[i]); 
		val+=Min,Min=1e18; 
		for(int i=x+1;i<=R;i++) Min=min(Min,g[i]); 
		ans=min(ans,Min+val+sum); 
		Min=1e18; 
		for(int i=max(0ll,x+1-k);i<x;i++){ 
			Min=min(Min,g[min(i+k,n+1)]); 
			ans=min(ans,f[i]+Min+sum); 
		} printf("%lld\n",ans); 
		if(st[x]) sum+=a[x],sum-=v; 
	} 
} 
signed main(){ 
	int T=read(); 
	while(T--) solve(); 
	return 0; 
} /*
1
10 3
5 10 7 100 4 3 12 5 100 1
0001000010
1
1 3

3
10 3
5 10 7 100 4 3 12 5 100 1
0001000010
2
2 3
6 15
5 6
1 1 1 1 1
00000
1
3 100
5 6
1 1 1 1 1
00100
1
3 100
*/