#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll dp[500001];
ll fp[500001];
int L[500001];
int R[500001];
char s[500005];
int id[500001];
int a[500001];
ll ans[500001];
int n,k,c;
inline ll get(int l,int r)
{
    dp[l]=0;deque<int>que;que.push_back(l);
    for(int i=l+1;i<=r;i++)
    {
        while(i-que.front()>k) que.pop_front();
        dp[i]=dp[que.front()]+a[i];
        while(dp[que.back()]>dp[i]) que.pop_back();
        que.push_back(i);
    }
    while(que.size()) que.pop_back();
    fp[r]=0;que.push_back(r);
    for(int i=r-1;i>=l;i--)
    {
        while(que.front()-i>k) que.pop_front();
        fp[i]=fp[que.front()]+a[i];
        while(fp[que.back()]>fp[i]) que.pop_back();
        que.push_back(i);
    }
    assert(dp[r]-a[r]==fp[l]-a[l]);
    return dp[r]-a[r];
}
inline void solve()
{
    n=read(),k=read(),a[0]=a[n+1]=c=0;
    for(int i=1;i<=n;i++) a[i]=read();
    scanf("%s",s+1);s[0]=s[n+1]='1';

    ll sum=0;
    for(int l=0,r;l<=n;l=r)
    {
        r=l+1;
        while(s[r]!='1') r++;
        // printf("l=%d r=%d\n",l,r);
        c++;for(int j=l+1;j<r;j++) id[j]=c;
        sum+=(ans[c]=get(l,r))+a[r];
        L[c]=l,R[c]=r;
    }

    int q=read();
    for(int i=1;i<=q;i++)
    {
        int x=read(),y=read();
        if(s[x]=='1') printf("%lld\n",sum-a[x]+y);
        else
        {
            int I=id[x];ll oth=sum-ans[I];
            ll o=oth+dp[x]+fp[x]-2*a[x]+y;

            ll mi=inf;
            for(int j=x+k-1;j>x;j--)
            {
                if(j-k>=L[I]) mi=min(mi,dp[j-k]);
                if(j<=R[I]) o=min(o,oth+mi+fp[j]);
            }
            printf("%lld\n",o);
        }
    }
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}