// happy

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

typedef pair<int,int> pii;
//typedef tuple<int,int,int> tp;
const int N = 1e6 + 2;
const int oo = 1e16;
//const int mod = 1e9 + 7;
//const int base = 29; // >= so pt pb max

int n, k, a[N], f[N], g[N], dp[2][N], L[N], R[N];

string s;

void solve(){
    cin >> n >> k;

    for(int i = 1; i <= n; i ++) cin >> a[i];

    cin >> s;
    s = " " + s;

    int dem = 0;

    deque<pii> dq;
    int tmp = 0;
    dq.push_back({0, 0});
    for(int i = 1; i <= n; i ++){
        while(!dq.empty() && dq.front().fi < i - k || dq.front().fi < tmp) dq.pop_front();

        f[i] = dq.front().se + a[i];
        while(!dq.empty() && dq.back().se > f[i]) dq.pop_back();
        dq.push_back({i, f[i]});
        if(s[i] == '1') tmp = i, dem += a[i];

        L[i] = tmp;

    }
    while(!dq.empty()) dq.pop_front();
    tmp = n + 1;
    dq.push_back({n + 1, 0});
    for(int i = n; i >= 1; i --){
        while(!dq.empty() && dq.front().fi > i + k || dq.front().fi > tmp) dq.pop_front();
        g[i] = dq.front().se + a[i];
        while(!dq.empty() && dq.back().se > f[i]) dq.pop_back();
        dq.push_back({i, g[i]});
        if(s[i] == '1') tmp = i;
        R[i] = tmp;

    }

    int q; cin >> q;

    while(q--){
        int x, v; cin >> x >> v;
        if(k > n){
            cout << dem + (s[x] == '1' ? v - a[x] : 0) << "\n";
            continue;
        }
        int now = a[x];
        a[x] = v;
        int l = max({0ll, x - k, L[x]});
        int r = min({n + 1, x + k, R[x]});
        int ret = oo, cnt = a[x];

//        for(int i = l; i <= r; i ++) dp[0][i] = dp[1][i] = 0;

        while(!dq.empty()) dq.pop_front();


        for(int i = l; i <= x - 1; i ++){
            dp[0][i] = f[i];
            while(!dq.empty() && dq.front().fi < i - k) dq.pop_front();
            while(!dq.empty() && dq.back().se > dp[0][i]) dq.pop_back();
            dq.push_back({i, dp[0][i]});
        }
        for(int i = x; i <= min(r, n); i ++){
            while(!dq.empty() && dq.front().fi < i - k) dq.pop_front();
            dp[0][i] = dq.front().se + a[i];
//            cout << i << " " << dq.front().se + g[i] << " hhh\n";
            if(i > x) ret = min(ret, dq.front().se + g[i]);
            else cnt += dq.front().se;
            while(!dq.empty() && dq.back().se > dp[0][i]) dq.pop_back();
            dq.push_back({i, dp[0][i]});
        }
        while(!dq.empty()) dq.pop_front();

        for(int i = r; i >= x + 1; i --){
            dp[1][i] = g[i];
            while(!dq.empty() && dq.front().fi > i + k) dq.pop_front();
            while(!dq.empty() && dq.back().se > dp[1][i]) dq.pop_back();
            dq.push_back({i, dp[1][i]});
        }

        for(int i = x; i >= max(l, 1ll); i --){
            while(!dq.empty() && dq.front().fi > i + k) dq.pop_front();
            dp[1][i] = dq.front().se + a[i];
//            cout << i << " " << dq.front().se + f[i] << " hhh\n";
            if(i < x) ret = min(ret, dq.front().se + f[i]);
            else cnt += dq.front().se;
            while(!dq.empty() && dq.back().se > dp[1][i]) dq.pop_back();
            dq.push_back({i, dp[0][i]});
        }


//        cout << cnt << " g\n";

        ret = min(ret, cnt);

        cout << ret << "\n";

        a[x] = now;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    int t; cin >> t;
    while(t--) solve();


}