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

typedef long long ll;

const int MAXN=5e5;
const ll INF=1e18;

inline int Read()
{
    int res;char c;
    while(1) {c=getchar();if('0'<=c && c<='9') {res=c-'0';break;}}
    while(1) {c=getchar();if('0'<=c && c<='9') res=res*10+c-'0';else break;}
    return res;
}

int T,n,K,A[MAXN+5],q;
bool S[MAXN+5];
ll f[MAXN+5],g[MAXN+5];
int Q[MAXN+5],Head,Tail;
ll ans;

int main()
{
    ios::sync_with_stdio(false);
    T=Read();
    while(T--)
    {
        n=Read(),K=Read();
        for(int i=1;i<=n;i++) A[i]=Read();
        string s;cin>>s;
        for(int i=1;i<=n;i++) S[i]=s[i-1]-'0';
        Q[Head=Tail=0]=0;
        for(int i=1;i<=n;i++)
        {
            while(i-Q[Head]>K) ++Head;
            f[i]=f[Q[Head]]+A[i];
            if(S[i]) Q[Head=Tail=0]=i;
            else
            {
                while(Head<=Tail)
                    if(f[i]<=f[Q[Tail]]) --Tail;
                    else break;
                Q[++Tail]=i;
            }
        }
        g[Q[Head=Tail=0]=n+1]=0;
        for(int i=n;i;i--)
        {
            while(Q[Head]-i>K) ++Head;
            g[i]=g[Q[Head]]+A[i];
            if(S[i]) Q[Head=Tail=0]=i;
            else
            {
                while(Head<=Tail)
                    if(g[i]<=g[Q[Tail]]) --Tail;
                    else break;
                Q[++Tail]=i;
            }
        }
        q=Read();
        for(int p,v;q--;)
        {
            p=Read(),v=Read();
            int L=p-1; while(L>max(p-K,0) && !S[L]) --L;
            int R=p+1; while(R<min(p+K,n+1) && !S[R]) ++R;
            ans=v;
            ll minn=INF; for(int i=L;i<p;i++) minn=min(minn,f[i]);
            ans+=minn;
            minn=INF; for(int i=R;i>p;i--) minn=min(minn,g[i]);
            ans+=minn;
            if(!S[p])
            {
                minn=INF; for(int i=p+1;i<=min(L+K,R);i++) minn=min(minn,g[i]);
                for(int i=L;i<p;i++)
                {
                    ans=min(ans,f[i]+minn);
                    if(i+K<R) minn=min(minn,g[i+K+1]);
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}