#pragma("ofast")
# include <bits/stdc++.h>
using namespace std;

# ifndef ONLINE_JUDGE
    # include "C:\Users\Kevin\Desktop\demo\save\debug.h"
# else
# define debug(...) 114514
# define ps 114514
# endif
struct Input {
    using i64 = long long;
    Input() {}
    static constexpr int MAXSIZE = 1 << 20;

    char buf[MAXSIZE], *p1 = buf, *p2 = buf;
    # define isdigit(x) ('0' <= x && x <= '9')
    
    #define gc()                                                                 \
       (p1 == p2 &&(p2 =(p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
            ? EOF                                                                \
            : *p1++)

    bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' || ch == EOF;
    }
    void tie(int x) {}
    template <typename T>
    Input &operator>>(T &x) {
        x = 0;
        bool sign = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if(ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) 
            x = (x << 3) + (x << 1) + ch - '0';
        if(sign) x = -x;
        return *this;
    }
    Input &operator>>(char &x) {
        x = ' ';
        for (; blank(x); x = gc());
        return *this;
    }
    Input &operator>>(double &x) {
        x = 0;
        double tmp = 1;
        bool sign = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if(ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) 
            x = x * 10 + ch - '0';
        if(ch == '.')
        for (ch = gc(); isdigit(ch); ch = gc())
            tmp /= 10.0, x += tmp *(ch - '0');
        if(sign) x = -x;
        return *this;
    }
    Input &operator>>(string &s) {
        s.clear();
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) {
            s += ch;
        }
        return *this;
    }
    # undef isdigit
    # undef gc
}input;
# define cin input
struct Output {
    struct setprecision {
        int precision;
    };
    static constexpr int MAXSIZE = 1 << 20;
    char pbuf[MAXSIZE], *pp = pbuf;
    void push(const char &c) { 
        if(pp - pbuf == MAXSIZE)                         
            fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf; 
        *pp++ = c;\
    }
    int precision;
    Output() { precision = 6;}
    ~Output() { fwrite(pbuf, 1, pp - pbuf, stdout);}
    char stack[40];
    int top = 0;
    template<class T>
    Output &operator<<(const T &x) {
        T tmp = x;
        bool _ = tmp < 0;
        if(_) tmp *= -1;
        while(tmp) stack[++ top] = '0' + tmp % 10, tmp /= 10;
        if(_) stack[++ top] = '-';
        while(top) push(stack [top]), -- top; 
        if(x == 0)push('0');
        return *this;
    }
    Output &operator<<(const string &x) {
        for (auto &u : x) push(u);
        return *this;
    }
    template<size_t N>
    Output &operator<<(const char(&x)[N]) {
        *this << string(x);
        return *this;
    }
    Output &operator<<(const char* const &x) {
        for (const char* ptr = x; *ptr != '\0'; ++ptr)
            push(*ptr);
        return *this;
    }
    Output &operator<<(const char &x) {
        push(x);
        return *this;
    }
    Output &operator<<(const bool &x) {
        push(x ? '1' : '0');
        return *this;
    }
    Output &operator<<(const double &x) {
        int intPart = static_cast<int>(x);
        *this << intPart;

        push('.');
        
        double decimalPart = x - intPart;
        for (int i = 0; i < precision; ++i) {
            decimalPart *= 10;
            int digit = static_cast<int>(decimalPart);
            *this << char('0' + digit);
            decimalPart -= digit;
        }
        return *this;
    }
    Output &operator<<(setprecision x) {
        precision = x.precision;
        return *this;
    }
    # undef push
}output;
# define cout output

using i64 = long long;
using ll = long long;
// #define int i64

/**
 * author:jiangly 
 * pretreatment:O(n)
 * Inquire:O(1) 
*/
template<class T,
    class Cmp = std::less<T>>
struct RMQ {
    const Cmp cmp = Cmp();
    static constexpr unsigned B = 64;
    using u64 = unsigned long long;
    int n;
    std::vector<std::vector<T>> a;
    std::vector<T> pre, suf, ini;
    std::vector<u64> stk;
    RMQ() {}
    RMQ(const std::vector<T> &v) {
        init(v);
    }
    void init(const std::vector<T> &v) {
        n = v.size();
        pre = suf = ini = v;
        stk.resize(n);
        if (!n) {
            return;
        }
        const int M = (n - 1) / B + 1;
        const int lg = std::__lg(M);
        a.assign(lg + 1, std::vector<T>(M));
        for (int i = 0; i < M; i++) {
            a[0][i] = v[i * B];
            for (int j = 1; j < B && i * B + j < n; j++) {
                a[0][i] = std::min(a[0][i], v[i * B + j], cmp);
            }
        }
        for (int i = 1; i < n; i++) {
            if (i % B) {
                pre[i] = std::min(pre[i], pre[i - 1], cmp);
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (i % B != B - 1) {
                suf[i] = std::min(suf[i], suf[i + 1], cmp);
            }
        }
        for (int j = 0; j < lg; j++) {
            for (int i = 0; i + (2 << j) <= M; i++) {
                a[j + 1][i] = std::min(a[j][i], a[j][i + (1 << j)], cmp);
            }
        }
        for (int i = 0; i < M; i++) {
            const int l = i * B;
            const int r = std::min(1U * n, l + B);
            u64 s = 0;
            for (int j = l; j < r; j++) {
                while (s && cmp(v[j], v[std::__lg(s) + l])) {
                    s ^= 1ULL << std::__lg(s);
                }
                s |= 1ULL << (j - l);
                stk[j] = s;
            } 
        } 
    } 
    T operator()(int l, int r) {
        if (l / B != (r - 1) / B) {
            T ans = std::min(suf[l], pre[r - 1], cmp);
            l = l / B + 1;
            r = r / B;
            if (l < r) {
                int k = std::__lg(r - l);
                ans = std::min({ans, a[k][l], a[k][r - (1 << k)]}, cmp);
            }
            return ans;
        } else {
            int x = B * (l / B);
            return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];
        }
    }
};

void solve () {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 2);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    } 
    string s;
    cin >> s;
    s = '1' + s + '1';
    vector<int> l(n + 2), r(n + 2, n + 1);
    for(int i = 1; i <= n; ++i) {
        if(s[i] == '1') l[i] = i;
        else l[i] = l[i - 1];
    }
    l[n + 1] = n + 1;
    for(int i = n; i >= 1; --i) {
        if(s[i] == '1') r[i] = i;
        else r[i] = r[i + 1];
    }
    r[0] = 0;

    vector<ll> disl(n + 2);
    {
        deque<int> q;
        q.push_back(0);
        disl[0] = 0;
        for(int i = 1; i <= n; ++i) {
            if(i == l[i]) {
                while(!q.empty() && (i - q.front() > k)) q.pop_front();
                // assert(!q.empty());
                int pos = q.front();
                disl[i] = (pos == l[pos] ? 0ll : disl[pos] + a[pos]);
                while(!q.empty()) q.pop_back();
            }
            else {
                while(!q.empty() && (i - q.front() > k)) q.pop_front();
                // assert(!q.empty());
                int pos = q.front();
                // debug(i, pos);
                disl[i] = (pos == l[pos] ? 0ll : disl[pos] + a[pos]);
                while(!q.empty()){
                    int pos = q.back();
                    ll val = (pos == l[pos] ? 0ll : disl[pos] + a[pos]);
                    if(val >= disl[i] + a[i]) q.pop_back();
                    else break;
                }
            }
            q.push_back(i);
        }
        disl[n + 1] = 0;
    }
    vector<ll> disr(n + 2);
    {
        deque<int> q;
        q.push_back(n + 1);
        disr[n + 1] = 0;
        for(int i = n; i >= 1; --i) {
            if(i == l[i]) {
                while(!q.empty() && (q.front() - i > k)) q.pop_front();
                assert(!q.empty());
                int pos = q.front();
                disr[i] = (pos == r[pos] ? 0ll : disr[pos] + a[pos]);
                while(!q.empty()) q.pop_back();
            }
            else {
                while(!q.empty() && (q.front() - i > k)) q.pop_front();
                assert(!q.empty());
                int pos = q.front();
                disr[i] = (pos == r[pos] ? 0ll : disr[pos] + a[pos]);
                while(!q.empty()){
                    int pos = q.back();
                    ll val = (pos == r[pos] ? 0ll : disr[pos] + a[pos]);
                    if(val >= disr[i] + a[i]) q.pop_back();
                    else break;
                }
            }
            q.push_back(i);
        }
        disr[0] = 0;
    }

    // + ai
    auto b = disl;
    for(int i = 0; i <= n + 1; ++i) b[i] += a[i];
    RMQ mnl(b);
    b = disr;
    for(int i = 0; i <= n + 1; ++i) {
        b[i] += a[i];
    }
    RMQ mnr(b);

    ll sum = 0;
    for(int i = 1; i <= n + 1; ++i) if(s[i] == '1') {
        sum += a[i];
        sum += disl[i];
    }

    int q;
    cin >> q;
    while(q --) {
        int p, v;
        cin >> p >> v;
        if(s[p] == '1') {
            ll ans = sum - a[p] + v;
            cout << ans << '\n';
        }
        else {
            // for(int i = max(l[i]))
            int L = l[p], R = r[p];
            if(R - L <= k) {
                cout << sum << '\n';
                continue;
            }
            ll ans = 1e18;
            if(p == L + 1) {
                ans = sum - disl[R] + disl[p] + disr[p] + v;
                for(int i = p + 1; i <= min(L + k, R - 1); ++i) {
                    ans = min(ans, sum - disl[R] + disr[i] + a[i]);
                }
            }
            else if(p == R - 1) {
                ans = sum - disl[R] + disl[p] + disr[p] + v;
                for(int i = p - 1; p >= max(R - k, L + 1); --i) {
                    ans = min(ans, sum - disl[R] + disl[i] + a[i]);
                } 
            }
            else {
                ans = sum - disl[R] + disl[p] + disr[p] + v;
                for(int i = max(L + 1, p - k + 1); i < p; ++i) {
                    // ans = min(ans, sum - disl[R] + disl[i] + )
                    if(i + k >= R) ans = min(ans, sum - disl[R] + disl[i] + a[i]);
                    else {
                        int sr = i + k;
                        if(sr < p + 1) continue;
                        ans = min(ans, sum - disl[R] + disl[i] + a[i] + mnr(p + 1, sr + 1));
                    }
                }
            }
            cout << ans << '\n';
        }
    }
} 
// 修一下爆没爆int
// 多测

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int t = 1;
    cin >> t;
	while (t --) {
        solve ();
	}
	return 0;
}