#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 arr[N],dp1[N],dp2[N],pre[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;
}

struct{
    #define pot(x) (1 << (x))

    int lg[N],dp[N][24];

    inline void build(){
        for (re int i = 2;i <= n + 1;i++) lg[i] = lg[i >> 1] + 1;
        for (re int i = 1;i <= n + 1;i++) dp[i][0] = dp2[i];
        for (re int j = 1;j <= lg[n + 1];j++){
            for (re int i = 1;i + pot(j) - 1 <= n + 1;i++) dp[i][j] = min(dp[i][j - 1],dp[i + pot(j - 1)][j - 1]);
        }
    }

    inline int query(int l,int r){
        int x = lg[r - l + 1];
        return min(dp[l][x],dp[r - pot(x) + 1][x]);
    }

    #undef pot
}T;

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';
    deque<pii> dq; dq.push_back({0,0});
    for (re int i = 1;i <= n + 1;i++){
        while (!dq.empty() && i - dq.front().fst > k) dq.pop_front();
        dp1[i] = dq.front().snd + arr[i]; pre[i] = dq.front().fst;
        while (!dq.empty() && dq.back().snd > dp1[i]) dq.pop_back();
        if (s[i] == '1') dq.clear(); dq.push_back({i,dp1[i]});
    }
    dq.clear(); dq.push_back({n + 1,0});
    for (re int i = n;~i;i--){
        while (!dq.empty() && dq.front().fst - i > k) dq.pop_front();
        dp2[i] = dq.front().snd + arr[i];
        while (!dq.empty() && dq.back().snd > dp2[i]) dq.pop_back();
        if (s[i] == '1') dq.clear(); dq.push_back({i,dp2[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;
}