#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 RMQ{
	vector<vector<ll>> jmp;
	RMQ(const vector<ll>&V) : jmp(1,V){
		for(int pw = 1,k = 1;pw * 2 <= sz(V);pw *= 2, ++k){
			jmp.emplace_back(sz(V) - pw*2+1);
			rep(j,0,sz(jmp[k]))
			   jmp[k][j] = min(jmp[k-1][j],jmp[k-1][j+pw]);
		}
	}
	ll query(int a,int b){
		assert(a<b);
		int dep = 31 - __builtin_clz(b-a);
		return min(jmp[dep][a],jmp[dep][b - (1<<dep)]);
	}
};
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';
		*/
		
		RMQ rmq(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--){
					int r = min(i+k,last);
					ans = min(ans,dp[i] + rmq.query(p+1,r+1));
					if(s[i])break;
				}
				
			}
			cout<<ans<<'\n';
		}
	}
}