#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <iterator>
#include <algorithm>
// #include <bit>
#include <numeric>
#include <iomanip>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<short, short> pss;
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define fi first
#define se second
#define MAX *max_element
#define MIN *min_element
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define bsi(x, v) (int) (lower_bound(x.begin(), x.end(), v) - x.begin())
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;

void smin(int& a, int b) {if (b<a) a=b;}
void smax(int& a, int b) {if (b>a) a=b;}
void smin(ll& a, ll b) {if (b<a) a=b;}
void smax(ll& a, ll b) {if (b>a) a=b;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        int a[n]; cina(a,n);
        string ss; cin >> ss;
        bool s[n]; forn(i,n) s[i] = (ss[i] == '1');
        ll pv[n+1], sv[n+1];
        int la[n], ra[n];
        forn(i,n+1) pv[i] = sv[i] = 0;
        int lb = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.push({0,0});
        forn(i,n) {
            smax(lb, i-k+1);
            while (pq.top().se < lb) pq.pop();
            pv[i+1] = pq.top().fi + a[i];
            pq.push({pv[i+1], i+1});
            la[i] = lb;
            if (s[i]) lb = i+1;
        }
        while (sz(pq)) pq.pop();
        lb = n;
        pq.push({0,n});
        for (int i = n-1; i>=0; i--) {
            smin(lb, i+k);
            while (pq.top().se > lb) pq.pop();
            sv[i] = pq.top().fi + a[i];
            pq.push({sv[i], i});
            ra[i] = lb;
            if (s[i]) lb = i;
        }
        // forn(i,n+1) cout << pv[i] spc;
        // nl;
        // forn(i,n+1) cout << sv[i] spc;
        // nl;
        // forn(i,n) cout << ra[i] spc;
        // nl;
        // forn(i,n) cout << la[i] spc;
        // nl;
        int q; cin >> q;
        while (q--) {
            int p, v; cin >> p >> v;
            p--;
            if (s[p]) {
                cout << pv[p+1] + sv[p] - 2*a[p] + v;
                continue;
            }
            ll ans = pv[p+1] + sv[p] - 2*a[p] + v;
            ll rm = inf2;
            forl(i,1,k) {
                // cout << p+i spc << p-k+i+1 el;
                if (p+i<=ra[p]) smin(rm, sv[p+i]);
                if (p-k+i+1>=la[p]) smin(ans, rm+pv[p-k+i+1]);
            }
            cout << ans el;
        }
    }
}