#include<iostream>
using namespace std;
#include<vector>
#include<string>

using i64 = long long;

const int N = 5e5 + 1;
vector<int> Log(N);

void init(){
	Log[1] = 0;
	for(int i = 2; i < N; ++i){
		Log[i] = Log[i >> 1] + 1;
	}
	return;
}

void build(vector<i64>& a, vector<vector<i64>>& st){
	st.assign(a.size(), vector<i64>(Log[a.size()]));
	for(int i = 0; i < a.size(); ++i) st[i][0] = a[i];
	for(int i = 1; i < Log[a.size()]; ++i){
		int d = 1 << (i - 1);
		for(int j = 0; j + (1 << i) < a.size(); ++j){
			st[j][i] = min(st[j][i - 1], st[j + d][i - 1]);
		}
	}
	return;
}

i64 tquery(int l, int r, vector<vector<i64>>& st){
	int L = Log[r - l + 1];
	return min(st[l][L], st[r - (1 << L) + 1][L]);
}

void solve(){
	i64 n, k;
	cin >> n >> k;

	vector<i64> a(n + 1);
	for(int i = 1; i <= n; ++i) cin >> a[i];

	string s;
    cin >> s;

    vector<i64> pref(n + 2), suff(n + 2);
    vector<i64> q(n + 2);
    int l = 0, r = -1;

    q[++r] = 0;
    for(int i = 1; i <= n + 1; ++i){
    	pref[i] = a[i] + pref[q[l]];
    	if(i != n + 1){
    		if(s[i - 1] == '0')
    			while(l <= r && pref[q[r]] > pref[i]) --r;
    		else r = l - 1;
    		q[++r] = i;
    		while(l <= r && i - q[l] >= k) ++l;
    	}
    }

    l = 0, r = -1;
    q[++r] = 0;
    for(int i = n; i >= 0; --i){
    	suff[i] = a[i] + suff[q[l]];
    	if(i != 0){
    		if(s[i - 1] == '0')
    			while(l <= r && suff[q[r]] > suff[i]) --r;
    		else r = l - 1;
	    	q[++r] = i;
    		while(l <= r && q[l] - i >= k) ++l;
    	}
    }

    vector<vector<i64>> st;
    build(pref, st);

    vector<i64> fn(n + 2), sn(n + 2);
    int t1 = 0, t2 = n + 1;
    fn[0] = 0;
    for(int i = 1; i <= n; ++i){
    	if(s[i] == '1') t1 = i;
    	if(s[n - i + 1] == '1') t2 = n - i + 1;
    	fn[i] = t1;
    	sn[n - i + 1] = t2;
    }

    int query = 0;
    cin >> query;

    for(int i = 0; i < query; ++i){
    	i64 p, v;
    	cin >> p >> v;
    	i64 ans = pref[p] + suff[p] - 2 * a[p] + v;
    	if(s[p - 1] == '0')
    	for(int j = p + 1; j <= min(p + k - 1, min(sn[p], n + 1)); ++j){
    		ans = min(ans, tquery(max(0LL, max(fn[p], j - k)), p - 1, st) + suff[j]);
    	}
    	cout << ans << "\n";
    }

    return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	init();

	int t = 1;
	cin >> t;
	while(t--) solve();

	return 0;
}
/*
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
*/