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

#define rep(i,a,b) for(int i=a;i < b;i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x.size())
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 5e5+5;
struct SPT
{
	vector<int>lg;
	vector<vector<ll>> s;
	//zero indexed
	//modify s and a to whatever type works
	SPT(int n,int lim,vector<ll>a)
	{
		s.resize(n);
		lg.resize(n+1);
		lg[1] = 0;
		for(int i=2;i<=n;i++)lg[i] = lg[i/2]+1;
		for(int i=0;i<n;i++){
			s[i].resize(lim+1);
			s[i][0] = a[i];
		}
		for(int k=1;k<=lim;k++){
			for(int i=0;i+(1<<k)-1<n;i++){
				s[i][k] = min(s[i][k-1] , s[i + (1<<(k-1))][k-1]);
			}
		}
	}
	ll query(int l,int r)
	{
		int j = lg[r-l+1];
		return min(s[l][j],s[r-(1<<j)+1][j]);
	}
};
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		vector<ll>a(n+2,0),dp(n+2,0),dp2(n+2,0);
		vector<int>s(n+2,0);
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++){
			char c;
			cin>>c;
			s[i] = c-'0';
		}
		int last = -1e9;
		multiset<ll>mn;
		mn.insert(0);
		for(int i=1;i<=n+1;i++){
			if(i-k-1 >= 0)mn.erase(mn.find(dp[i-k-1]));
			if(last >= i-k)dp[i] = dp[last] + a[i];
			else{
				dp[i] = *mn.begin()+a[i];
			}
			mn.insert(dp[i]);
			if(s[i])last = i;
		}
		
		last = 1e9;
		mn.clear();
		mn.insert(0);
		for(int i=n;i>=0;i--){
			if(i+k+1 <= n+1)mn.erase(mn.find(dp2[i+k+1]));
			if(last <= i+k)dp2[i] = dp2[last] + a[i];
			else{
				dp2[i] = *mn.begin()+a[i];
			}
			mn.insert(dp2[i]);
			if(s[i])last = i;
		}
		/*
		for(int i=0;i<=n+1;i++)cout<<dp[i]<<" ";
		cout<<'\n';
		for(int i=0;i<=n+1;i++)cout<<dp2[i]<<" ";
		cout<<'\n';
		*/
		
		SPT rmq(n+2,19,dp2);
		int q;
		cin>>q;
		while(q--){
			int p;
			ll v;
			cin>>p>>v;
			ll ans = 1e18;
			int last = 1e9;
			for(int i=p+1;i<=min(p+k,n+1);i++){
				ans = min(ans,dp[p] -a[p] + v + dp2[i]);
				if(s[i]){
					last = i;
					break;
				}
			}
			if(!s[p]){
				for(int i=p-1;i>=max(0,p-k+1);i--){
					//for(int j=p+1;j<=min(last,i+k);j++)ans = min(ans,dp[i] + dp2[j]);
					int r = min(i+k,last);
					ans = min(ans,dp[i] + rmq.query(p+1,r));
					if(s[i])break;
				}
				
			}
			cout<<ans<<'\n';
		}
	}
}