#include <bits/stdc++.h>
#define int long long

using namespace std;

const int inf = 1E18;

inline int read () {
    int w = 1, s = 0; char ch = getchar ();
    for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') w = -1;
    for (; isdigit (ch); ch = getchar ()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

void solve () {
	int n, k;
    cin >> n >> k;
    
    vector <int> a (n + 2);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    string s;
    cin >> s;

    s = " " + s + "0";

    //f从前往后，g从后往前
    vector <int> f (n + 2), g (n + 2);
    
    auto work1 = [&] (vector <int> &dp) {
        deque <int> q;
        q.push_back (0);
        for (int i = 1; i <= n + 1; i ++) {
            while (q.size () && q.front () < i - k) {
                q.pop_front ();
            }
            dp[i] = dp[q.front ()] + a[i];
            if (s[i] == '1') {
                q.clear ();
            }
            while (q.size () && dp[q.back ()] >= dp[i]) {
                q.pop_back ();
            }
            q.push_back (i);
        }
    };

    work1 (f);
    reverse (s.begin () + 1, s.end ());
    reverse (a.begin () + 1, a.end ());
    work1 (g);
    reverse (s.begin () + 1, s.end ());
    reverse (a.begin () + 1, a.end ());
    reverse (g.begin () + 1, g.end ());
    
    for (int i = 1; i <= n; i ++) {
        g[i] -= a[i];
    }

    vector <int> h (n + 2);
    auto work2 = [&] (int x, int y) -> int {
        int ans = inf;
        int old = a[x];
        a[x] = y;

        deque <int> q;
        for (int i = k; i > 0; i --) {
            if (x - i >= 0) {
                if (s[x - i] == '1') {
                    q.clear ();
                }
                while (q.size () && f[q.back ()] >= f[x - i]) {
                    q.pop_back ();
                }
                q.push_back (x - i);
            }
        }
        for (int i = x; i < x + k && i <= n + 1; i ++) {
            while (q.size () && q.front () < i - k) {
                q.pop_front ();
            }
            if (q.front () < x) {
                h[i] = f[q.front ()] + a[i];
            } else {
                h[i] = h[q.front ()] + a[i];
            }
            ans = min (ans, h[i] + g[i]);
            if (s[i] == '1') {
                q.clear ();
            }
            while (q.size () && (q.back () < x ? f[q.back ()] : h[q.back ()]) >= h[i]) {
                q.pop_back ();
            }
            q.push_back (i);
        }
        return ans;
    };

    int q;
    cin >> q;

    while (q --) {
        int p, v;
        cin >> p >> v;

        cout << work2 (p, v) << '\n';
    }
} 

signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);
    
	int T = 1; 
	cin >> T;
	// T = read ();

	while (T --) {
		solve ();
	}
	
	return 0;
}