#include<bits/stdc++.h>
#include<numeric>
using namespace std;
template<typename typC,typename typD> bool cmin(typC &x,const typD &y) { if (y<x) { x=y; return 1; } return 0; }
template<typename typC,typename typD> bool cmax(typC &x,const typD &y) { if (x<y) { x=y; return 1; } return 0; }
#define ll long long
#define pb emplace_back
#define fs first
#define sc second
#define pi pair<ll,ll>
#define mpi make_pair
#define re(a) {cout<<a<<endl;return;}
#define all(v) v.begin(),v.end()
#define fr(i,a,n)  for(int i=a;i<=n;i++)
const int N = 2e2+ 7;
const ll inf = 1e15;
const int mod =1e9+7;
//#define cin fin
//ifstream fin("in.txt",ios::in);
//function<void(int,int)>dfs=[&](int x,int y)->void{};
struct Smaldeque{
    int k;
    deque<pair<int,ll>>dq;
    void push(int p,ll px){
        while(!dq.empty()){
            if(px>dq.back().second){
                dq.push_back({p,px});
                break;
            }
            else    dq.pop_back();
        }
        if(dq.empty()){
            dq.push_back({p,px});
        }
        if(p-dq.front().first>=k){
            dq.pop_front();
        }
    };
    int mi(){
        return dq.front().second;
    }
};
void solve() {
    ll n,k;    cin>>n>>k;
    vector<ll>a(n+3,0),b(n+2,0),pre(n+3,0),suf(n+3,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    a[n+1]=0;
    string s;   cin>>s;
    ll ans=0;
    for(int i=0;i<s.size();i++)
        if(s[i]=='1'){
            ans+=a[i+1];
            a[i+1]=0;
        }
    Smaldeque dq1,dq2;
    dq1.k=k;    dq2.k=k;
    dq1.push(0,0);
    dq2.push(0,0);
    for(int i=1;i<=n+1;i++){
        pre[i]=dq1.mi()+a[i];
        dq1.push(i,pre[i]);
    }
    for(int i=n+1;i>=0;i--){
        suf[i]=dq2.mi()+a[i];
        dq2.push(n+2-i,suf[i]);
    }
    int q;  cin>>q;
    while(q--){
        ll add=0;
        ll p,v;    cin>>p>>v;
        if(s[p-1]=='1') cout<<ans-b[p]+v<<"\n";
        else{
            Smaldeque dqq;
            dqq.k=k;
            for(ll i=max(0ll,p-k+1);i<p;i++){
                dqq.push(i,pre[i]);
            }
            dqq.push(p,pre[p]-a[p]+v);
            add=pre[p]+suf[p]-2*a[p]+v;
            for(int i=p+1;i<=min(p+k-1,(ll)n+1);i++){
                add=min(dqq.mi()+suf[i],add);
                dqq.push(i,dqq.mi()+a[i]);
            }
            cout<<ans+add<<"\n";
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
//  #ifdef LOCAL
//  freopen("in.txt", "r", stdin);
//  #endif
    int _ = 1;
    cin >> _;//处理多组样例T
    while (_--) solve();
}