#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        ll n,k;
        cin >> n >> k;
        vector<ll> v(n+2);
        vector<ll> dp1(n+2,1e18);
        vector<ll> dp2(n+2,1e18);
        dp1[0] =0;
        dp2[n+1] = 0;
        set<pair<ll,ll>> aux;
        FOR(i,1,n+1) cin >> v[i];
        string s;
        cin >> s;
        int last = 0;
        aux.insert({0,0});
        s.push_back('#');
        for(int i = 1; i <= n; i++){
                if(i-last > k){
                    aux.erase({dp1[last],last});
                    last++;
                }
                pair<ll,ll> pa = *aux.begin();
                dp1[i] = pa.first+v[i];
                aux.insert({dp1[i],i});
                if(i!= (n+1) &&s[i-1] == '1'){
                    for(int j = last; j <i; j++){
                        aux.erase({dp1[j],j});
                    }
                    last = i;
                }
        }
        for(ll i = n; i>= max(0LL,n-k);i--) dp1[n+1] = min(dp1[i],dp1[n+1]);
        aux.clear();
        last = n+1;
        aux.insert({0,n+1});
        for(int i = n; i >= 1; i--){
                if(last-i > k){
                    aux.erase({dp2[last],last});
                    last--;
                }
                pair<ll,ll> pa = *aux.begin();
                dp2[i] = pa.first+v[i];
                aux.insert({dp2[i],i});
                if(i >0 && s[i-1] == '1'){
                    for(int j = last; j >i; j--){
                        aux.erase({dp2[j],j});
                    }
                    last = i;
                }
        }
        for(ll i = 1; i<= min(n+1,k); i++) dp2[0] = min(dp2[i],dp2[0]);
        aux.clear();
        int q;
        cin >> q;
        for(int i = 0; i < q; i++){
            ll a,b;
            cin >> a >> b;
            ll ans = dp1[a]+dp2[a]-2*v[a]+b;
            if(s[a-1] == '1'){
                cout <<ans<<'\n';
                continue;
            }
            ll mn = dp2[a+1];
            bool ok = true;
            for(int j = max(0LL,a+1-k); j < a; j++){

                if(ok && j+k <= n+1) mn = min(mn,dp2[j+k]);
                ans = min(ans,dp1[j]+mn);
                if(s[j+k-1] == '1'){
                    ok = false;
                }
            }
            cout <<ans<<'\n';
        }
    }
}