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

using namespace std;

const int N = 5e5 + 10, INF = 0x3f3f3f3f;

int T, n, m, k, hd, ed;
int a[N], q[N], q2[N], fr[N], x[N], v[N], id[N];
int f[N], tf[N], g[N], ans[N];
char s[N];

bool cmp(int a, int b) {
    return x[a] < x[b];
}

signed main() {
    cin >> T;
    while(T --) {
        cin >> n >> k;
        for(int i = 1; i <= n; i ++) cin >> a[i];

        cin >> s + 1;

        a[0] = a[n + 1] = f[0] = 0;
        q[hd = ed = 1] = 0;

        for(int i = 1; i <= n + 1; i ++) {
            while(q[hd] < i - k) hd ++;
            f[i] = f[q[hd]] + a[i];

            if(s[i] == '1') q[hd = ed = 1] = i;
            else {
                while(ed >= hd && f[q[ed]] >= f[i]) ed --;
                q[++ ed] = i;
            }
        }

        q[hd = ed = 1] = n + 1;
        fr[n + 1] = n + 1;
        g[n + 1] = 0;

        for(int i = n; i >= 0; i --) {
            while(q[hd] > i + k) hd ++;

            g[i] = g[q[hd]] + a[i];
            fr[i] = q[hd];

            if(s[i] == '1') q[hd = ed = 1] = i;
            else {
                while(ed >= hd && g[q[ed]] >= g[i]) ed --;
                q[++ ed] = i;
            }
        }

        cin >> m;
        for (int i = 1; i <= m; ++i)    scanf("%d%d", &x[i], &v[i]), id[i] = i, ans[i] = INF;
        sort(id + 1, id + m + 1, cmp);
        q[hd = ed = 1] = 0;
        int cur = 1;
        for (int i = 1; i <= n; ++i) {
            while (q[hd] < i - k)   ++hd;
            while (x[id[cur]] == i && cur <= m) {
                int hd2 = hd, ed2 = ed, t = a[i];
                a[i] = v[id[cur]];
                for (int j = hd; j <= ed; ++j)  q2[j] = q[j];
                int mx = min(i + k, n + 1);
                for (int j = i; j <= mx; ++j) {
                    while (q2[hd2] < j - k)   ++hd2;
                    tf[j] = tf[q2[hd2]] + a[j];
                    ans[id[cur]] = min(ans[id[cur]], tf[j] + g[fr[j]]);
                    if (s[j] == '1')    q2[hd2 = ed2 = 1] = j;
                    else {
                        while (ed2 >= hd2 && tf[q2[ed2]] > tf[j]) --ed2;
                        q2[++ed2] = j;
                    }
                }
                a[i] = t;
                ++cur;
            }
            tf[i] = tf[q[hd]] + a[i];
            if (s[i] == '1')    q[hd = ed = 1] = i;
            else {
                while (ed >= hd && f[q[ed]] > f[i]) --ed;
                q[++ed] = i;
            }
        }
        for (int i = 1; i <= m; ++i)    printf("%lld\n", ans[i]);
    }
}