#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7/*998244353*/;

const int N=5e5+5,K=3e3+5;

int n,k,q;
ll a[N];
bool mst[N];
ll f[N],g[N],t[N];
int hd,tl;
int pq[N];
void init(){
    pq[hd=tl=0]=0;
    f[0]=0;
    rep(i,1,n+1){
        while(hd<=tl&&i-pq[hd]>k)hd++;
        f[i]=f[pq[hd]]+a[i];
        while(hd<=tl&&f[pq[tl]]>=f[i])tl--;
        pq[++tl]=i;
        if(mst[i])hd=tl;
    }
    reverse(a+1,a+1+n);
    reverse(mst+1,mst+1+n);
    g[0]=0;
    pq[hd=tl=0]=0;
    rep(i,1,n+1){
        while(hd<=tl&&i-pq[hd]>k)hd++;
        g[i]=g[pq[hd]]+a[i];
        while(hd<=tl&&g[pq[tl]]>=g[i])tl--;
        pq[++tl]=i;
        if(mst[i])hd=tl;
    }
    reverse(g,g+1+n+1);
    reverse(a,a+1+n+1);
    reverse(mst+1,mst+1+n);
}

int p;
ll v;

void solve(){
    cin>>n>>k;
    rep(i,1,n)cin>>a[i];
    char c;
    rep(i,1,n){cin>>c;mst[i]=c-'0';}
    init();
    cin>>q;
    while(q--){
        cin>>p>>v;
        if(mst[p]){
            cout<<f[p]-a[p]+g[p]-a[p]+v<<"\n";
        }else{
            t[p]=f[p]-a[p]+v;
            int lb=p;
            ll ans=f[p]-a[p]+g[p]-a[p]+v;
            per(i,p-1,max(0,p-k)){
                t[i]=min(t[i+1],f[i]);
                chmin(lb,i);
                if(mst[i])break;
            }
            rep(i,p+1,min(n+1,p+k)){
                chmin(ans,t[i-k]+g[i]);
                if(mst[i])break;
            }
            cout<<ans<<"\n";
        }
    }
}

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