#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long
#define chmin(a,b) (a = min(a,b))

using namespace std;

typedef pair<int,int> pii;
const int N = 5e5 + 10;
const int inf = (int)(1e18) + 10;
int n,k,q;
char s[N];
int hh,tt,dq[N];
int arr[N],dp1[N],dp2[N],tmp[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void solve(){
    fill(dp1,dp1 + n + 5,0);
    fill(dp2,dp2 + n + 5,0);
    n = read(),k = read();
    for (re int i = 1;i <= n;i++) arr[i] = read();
    scanf("%s",s + 1); q = read();
    s[0] = s[n + 1] = '1';
    hh = 1,tt = 0; dq[++tt] = 0;
    for (re int i = 1;i <= n + 1;i++){
        while (hh <= tt && i - dq[hh] > k) hh++;
        dp1[i] = dp1[dq[hh]] + arr[i];
        while (hh <= tt && dp1[dq[tt]] > dp1[i]) tt--;
        if (s[i] == '1') hh = tt = 0; dq[++tt] = i;
    }
    hh = 1,tt = 0; dq[++tt] = n + 1;
    for (re int i = n;~i;i--){
        while (hh <= tt && dq[hh] - i > k) hh++;
        dp2[i] = dp2[dq[hh]] + arr[i];
        while (hh <= tt && dp2[dq[tt]] > dp2[i]) tt--;
        if (s[i] == '1') hh = 1,tt = 0; dq[++tt] = i;
    }
    while (q--){
        int x,v;
        x = read(),v = read();
        int ans = dp1[x] + dp2[x] - 2 * arr[x] + v;
        if (s[x] == '1'){
            printf("%lld\n",ans); continue;
        }
        int r = min(n + 1,x + k);
        int prex = arr[x],pos = x - k + 1; arr[x] = v;
        tmp[x] = dp1[x] - prex + v;
        for (re int i = x - 1;i >= min(0ll,x - k);i--){
            tmp[pos = i] = min(dp1[i],tmp[i + 1]);
            if (s[i] == '1') break;
        }
        for (re int i = x + 1;i <= r;i++){
            chmin(ans,tmp[max(pos,i - k)] + dp2[i]);
            if (s[i] == '1') break;
        }
        printf("%lld\n",ans); arr[x] = prex;
    }
}

signed main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}