#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;



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 = '1' + s + '1';
    int q;
    cin >> q;
    vector<vector<pii> > que(n + 1);
    for(int i = 1; i <= q; i ++ ) {
        int pos, v;
        cin >> pos >> v;
        que[pos].push_back({v, i});
    }
    vector<ll> g(n + 2);
    deque<ll> dq;
    dq.push_back(n + 1);
    for(int i = n; i >= 1; i -- ) {
        while(dq.size() && i + k < dq.front()) {
            // cout << '?' << i << ' ' << dq.front() << '\n';
            dq.pop_front();
        }
        // cout << "h" << i << ' ' << dq.front() << '\n';
        g[i] = g[dq.front()] + a[i];
        while(dq.size() && g[i] <= g[dq.back()]) {
            // cout << '!' << i << ' ' << dq.back() << '\n';
            dq.pop_back();
        }
        if(s[i] == '1') {
            while(dq.size()) dq.pop_front();
        }
        dq.push_back(i);
        // cout << i << ' ' << g[i] << '\n';
    }
    // cout << '\n';

    vector<ll> f(n + 2);
    while(dq.size()) dq.pop_front();
    dq.push_back(0);
    vector<ll> ans(q + 1, 1e18);
    for(int i = 1; i <= n; i ++ ) {
        while(dq.size() && i - k > dq.front()) {
            dq.pop_front();
        }
        int tmp = a[i];
        for(auto [v, num] : que[i]) {
            auto ndq = dq;
            a[i] = v;
            for(int j = i; j <= min(n + 1, i + k - 1); j ++ ) {
                while(ndq.size() && j - k > ndq.front()) {
                    ndq.pop_front();
                }
                f[j] = f[ndq.front()] + a[j];
                // cout << ndq.front() << ' ' << f[ndq.front()] << '\n';
                // if(i != j) {
                //     cout << j << ' ' << f[j] << ' ' << g[j] << ' ' << a[j] << ' ' << f[j] + g[j] - a[j] << '\n';
                // } else {
                //     cout << j << ' ' << f[j] << ' ' << g[j] << ' ' << tmp << ' ' << f[j] + g[j] - tmp << '\n';
                // }
                while(ndq.size() && f[j] <= f[ndq.back()]) {
                    // cout << '!' << j << ' ' << dq.back() << '\n';
                    ndq.pop_back();
                }
                if(s[j] == '1') {
                    while(ndq.size()) {
                        ndq.pop_front();    
                    } 
                }
                ndq.push_back(j);
                if(j == i) {
                    ans[num] = min(ans[num], f[j] + g[j] - tmp);
                } else {
                    ans[num] = min(ans[num], f[j] + g[j] - a[j]);
                }
            }
            // cout << '\n';
        }
        a[i] = tmp;
        f[i] = f[dq.front()] + a[i];
        // if(que.size()) {
        //     for(int j = i + 1; j <= min(n + 1, i + k - 1); j ++ ) {
        //         f[j] = 0;
        //     }
        // }
        if(s[i] == '1') {
            while(dq.size()) dq.pop_front();
        }
        dq.push_back(i);
    }

    for(int i = 1; i <= q; i ++ ) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t = 1;
    cin >> t;
    while(t -- ) {
        solve();
    }
    
    return 0;
}