#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 ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define pb push_back
#define mp make_pair

#define MAXN 500'010


template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& 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]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

int n, k;
ll a[MAXN];
string s;
ll dp[MAXN];
vector<ll> dp2;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
    
    cin >> n >> k;
    dp2.resize(n);
    rep(i, 0, n) cin >> a[i];
    cin >> s;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.push(mp(0, -1));
    rep(i, 0, n) {
        while (q.top().second < i-k) q.pop();
        dp[i] = q.top().first + a[i];
        if (s[i] == '1') {
            while (!q.empty()) q.pop();
        }
        q.push(mp(dp[i], i));
    }
    while (!q.empty()) q.pop();
    q.push(mp(0, n));
    for (int i = n-1; i >= 0; i--) {
        while (q.top().second > i+k) q.pop();
        dp2[i] = q.top().first + a[i];
        if (s[i] == '1') {
            while (!q.empty()) q.pop();
        }
        q.push(mp(dp2[i], i));
    }

    RMQ<ll> rt(dp2);

    int numq;
    cin >> numq;
    //cout << numq << endl;
    while (numq--) {
        int ind;
        ll newval;
        cin >> ind >> newval;
        ind--;

        ll includecost = newval;
        {
        ll leftcost = 0;
        if (ind >= k) leftcost = dp[ind-1];
        for (int i = ind-1; i >= max(0, ind-k); i--) {
            leftcost = min(leftcost, dp[i]);
            if (s[i] == '1') break;
        }

        ll rightcost = 0;
        if (ind < n-k) rightcost = dp2[ind+1];
        for (int i = ind+1; i <= min(n-1, ind+k); i++) {
            rightcost = min(rightcost, dp2[i]);
            if (s[i] == '1') break;
        }

        includecost += rightcost + leftcost;
        }

        ll excludecost = -1;
        {
        int nextrights = n;
        for (int i = ind+1; i <= min(n-1, ind+k); i++) {
            if (s[i] == '1') {
                nextrights = i;
                break;
            }
        }

        for (int i = ind-1; i >= max(-1, ind-k+1); i--) {
            ll med = 0;
            if (i != -1) med = dp[i];
            if (i < n-k || nextrights < n) med += rt.query(ind+1, min(nextrights+1, i+k+1)); // include something to the right
            if (excludecost == -1 || med < excludecost) excludecost = med;
        }
        }
        if (s[ind] == '1' || excludecost == -1) excludecost = includecost;
        cout << min(excludecost, includecost) << '\n';
        //cout << excludecost << ' ' << includecost << endl;

        
    }


    }
}