#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";

using namespace std;
const int Mod = 998244353;
const int N = 5e5 + 10;
using ll = long long;
ll n, k, a[N], b[N], lf[N], L, R, que[N], rf[N], p, v, q, fir, minnn, minn, c[N];
char ch;

ll min(ll a, ll b) { return a < b ? a : b; }
ll max(ll a, ll b) { return a > b ? a : b; }

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> ch;
        b[i] = 0;
        if (ch == '1')
            b[i] = i;
        else
            b[i] = b[i - 1];
    }
    for (int i = n; i > 0; i--)
        if (b[i] == i)
            c[i] = i;
        else
            c[i] = c[i + 1];
    b[0] = c[0] = 0;
    b[n + 1] = c[n + 1] = n + 1;
    a[0] = a[n + 1] = 0;
    rf[n + 1] = 0;
    lf[0] = 0;
    L = 0;
    R = 1;
    que[1] = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        while (que[L + 1] <= i - k - 1)
            L++;
        lf[i] = lf[que[L + 1]] + a[i];
        if (b[i] != i)
        {
            while (R > L && lf[i] < lf[que[R]])
                R--;
            que[++R] = i;
        }
        else
        {
            que[++R] = i;
            L = R - 1;
        }
    }
    L = 0;
    R = 1;
    que[1] = n + 1;
    for (int i = n; i >= 0; i--)
    {
        while (que[L + 1] >= i + k + 1)
            L++;
        rf[i] = rf[que[L + 1]] + a[i];
        if (b[i] != i)
        {
            while (R > L && rf[i] < rf[que[R]])
                R--;
            que[++R] = i;
        }
        else
        {
            que[++R] = i;
            L = R - 1;
        }
    }
    cin >> q;
    while (q--)
    {
        cin >> p >> v;
        if (b[p] == p)
        {
            cout << lf[n + 1] - a[p] + v << '\n';
            continue;
        }
        minn = lf[p] + rf[p] - 2 * a[p] + v;
        fir = max(b[p], p - k + 1);
        minnn = L_INF;
        for (int i = p + 1; i < fir + k && i <= c[p]; i++)
            minnn = min(minnn, rf[i]);
        for (int i = fir; i < p; i++)
        {
            if (i + k <= c[p])
                minnn = min(minnn, rf[i + k]);
            minn = min(minn, lf[i] + minnn);
        }
        cout << minn << '\n';
    }
}
int main()
{
    IOS;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#ifndef ONLINE_JUDGE
    clock_t start_time = clock();
#endif
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
#ifndef ONLINE_JUDGE
    cout << "Used " << (double)(clock() - start_time) << " ms" << endl;
#endif
    return 0;
}