#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}
 
template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const ld pi = 3.14159265358979323846;
const int mod = 998244353;
const ll INF = 1e18;

const int N = (int)1e5 + 1, M = N * 2;

void solve(){
    int n, m;
    cin >> n >> m;

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

    string s;
    cin >> s;

    ll f[n + 1], g[n + 2];
    for(int i = 0; i <= n; i++){
        f[i] = g[i] = INF;
    }
    g[n + 1] = 0;

    deque<int> q;
    f[0] = 0;
    q.pb(0);

    for(int i = 1; i <= n; i++){
        if(!q.empty()){
            if(q.front() < i - m){
                q.pop_front();
            }
            f[i] = chmin(f[i], f[q.front()] + a[i]);
        }

        if(s[i - 1] == '1'){
            q.clear();
        }
        while(!q.empty() && f[q.back()] >= f[i]){
            q.pop_back();
        }
        q.pb(i);
    }

    q.clear();
    q.pb(n + 1);

    for(int i = n; i >= 1; i--){
        if(!q.empty()){
            if(q.front() > i + m){
                q.pop_front();
            }
            g[i] = chmin(g[i], g[q.front()] + a[i]);
        }

        if(s[i - 1] == '1'){
            q.clear();
        }
        while(!q.empty() && g[q.back()] >= g[i]){
            q.pop_back();
        }
        q.pb(i);
    }

    int k;
    cin >> k;

    for(int i = 1; i <= k; i++){
        int p, v;
        cin >> p >> v;

        int t = a[p];
        a[p] = v;

        int l = chmax(p - m - 1, 0), r = chmin(p + m + 1, n + 1);
        q.clear();

        ll b[r - l + 1], c[r - l + 1];
        for(int j = l; j <= r; j++){
            b[j - l] = f[j];
            c[j - l] = g[j];
            f[j] = g[j] = INF;
        }

        q.pb(l);
        f[l] = b[0];
        ll qwq = INF;

        for(int j = l + 1; j <= r; j++){
            if(!q.empty()){
                if(q.front() < j - m){
                    q.pop_front();
                }
                f[j] = chmin(f[j], f[q.front()] + a[j]);
            }

            if(s[j - 1] == '1'){
                q.clear();
            }
            while(!q.empty() && f[q.back()] >= f[j]){
                q.pop_back();
            }
            q.pb(j);
        }

        q.clear();
        q.pb(r);
        g[r] = c[r - l];

        for(int j = r - 1; j >= l; j--){
            if(!q.empty()){
                if(!q.front() > j + m){
                    q.pop_front();
                }
                g[j] = chmin(g[j], g[q.front()] + a[j]);
            }

            if(s[j - 1] == '1'){
                q.clear();
            }
            while(!q.empty() && g[q.back()] >= g[j]){
                q.pop_back();
            }
            q.pb(j);
        }

        q.clear();
        q.pb(l);
        for(int j = l + 1; j <= r; j++){
            if(!q.empty()){
                if(q.front() < j - m){
                    q.pop_front();
                }
                qwq = chmin(qwq, g[j] + f[q.front()]);
            }

            if(s[j - 1] == '1'){
                q.clear();
            }
            while(!q.empty() && f[q.back()] > f[j]){
                q.pop_back();
            }
            q.pb(j);
        }

        for(int j = l; j <= r; j++){
            f[j] = b[j - l];
            g[j] = c[j - l];
        }
        a[p] = t;
        cout << qwq << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;

    while(t--){
        solve();
    }
    
    return 0;
}