#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;

int t,n,k,qu;

string s;

struct node{
    long long val, ord;
};

void solve(){
    deque<node> q;
    cin>>n>>k;
    vector<long long> a(n*2+10), predp(n*2+10), sufdp(n*2+10);
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    cin>>s;
    s = s + "  ";
    for(int i = 0;i<=n+1;i++){
        while(!q.empty() && q.front().ord < i-k)q.pop_front();
        if(i<=1)predp[i] = a[i];
        else{
            predp[i] = a[i] + q.front().val;
            if(s[i-1] == '1'){
                q.clear();
            }
            while(!q.empty() && q.back().val > predp[i])q.pop_back();   
        }
        q.push_back(node{predp[i], i});
    }
    q.clear();
    for(int i = n+1;i>=0;i--){
        while(!q.empty() && q.front().ord > i + k)q.pop_front();
        if(i>=n)sufdp[i] = a[i];
        else{
            sufdp[i] = a[i] + q.front().val;
            if(i !=0 &&s[i-1] == '1'){
                q.clear();
            }
            while(!q.empty() && q.back().val > sufdp[i])q.pop_back();   
        }
        q.push_back(node{sufdp[i], i});
    }
    cin>>qu;
    while(qu--){
        long long p,v;
        cin>>p>>v;
        if(s[p-1] == '1'){
            cout<<predp[n+1] - a[p]+v<<'\n';
            continue;
        }
        if(a[p]>=v)
        {
            long long l=max(0ll,p-k);
            long long prex=1e18;
            for(int i=p-1;i>=l;i--)
            {
                if(i!=0&&s[i-1]=='1')
                {
                    prex=predp[i];
                    break;
                }
                prex=min(prex,predp[i]);
            }
            long long r=min((long long)(n+1),p+k);
            long long sufx=1e18;
            for(int i=p+1;i<=r;i++)
            {
                if(i!=n+1&&s[i-1]=='1')
                {
                    sufx=sufdp[i];
                    break;
                }
                sufx=min(sufx,sufdp[i]);
            }
            cout<<min(v+prex+sufx,predp[n+1])<<'\n';
        }
        else
        {
            long long l=max(0ll,p-k+1);
            long long r=min((long long)n+1,p+k-1);
            long long res=1e18;
            q.clear();
            for(int i=l;i<p;i++)
            {
                if(i!=0&&s[i-1]=='1')
                {
                    l=i;
                }
            }
            for(int i=r;i>p;i--)
            {
                if(i!=n+1&&s[i-1]=='1')
                {
                    r=i;
                }
            }
            if(r-l<=k)
            {
                cout<<min(predp[l]+sufdp[r],predp[n+1]+v-a[p])<<'\n';
                continue;
            }
            else
            {
                int j=l+k;
                long long sufx=1e18;
                for(int i=p+1;i<=j;i++)
                {
                    sufx=min(sufx,sufdp[i]);
                }
                long long res=1e18;
                for(int i=l;i<p;i++)
                {
                    res=min(predp[i]+sufx,res);
                    //cout<<"!"<<i<<" "<<sufdp[i]<<" "<<sufx<<" "<<res<<endl;
                    if(j<=r)
                    {
                    j++;
                    sufx=min(sufx,sufdp[j]);
                    }
                }
                cout<<min(res,predp[n+1]+v-a[p])<<'\n';
                continue;
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}