#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pi;
#define int ll
#define X first
#define Y second
#define fer(i,a,n) for(int i=a;i<=n;i++)
#define ref(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define mem(a,x) memset(a,x,sizeof a)
#define ac IO;int t;cin>>t;while(t--)solve()
#define AC signed main(){IO;solve();}
#define NO {cout<<"No"<<endl;return;}
#define YES {cout<<"Yes"<<endl;return;}
#define re(a) {cout<<a<<endl;return;}
#define all(v) v.begin(),v.end()
//ofstream fout("out.txt", ios::out);
//ifstream fin("in.txt", ios::in);
//#define cout fout
//#define cin fin
//--------------------瑞神神中神--------------------
//--------------------刘魔魔中魔--------------------

const int N=5e5+10;
int a[N],f[N],g[N],dp[N];
vector<int>vec;
pi q[N];
int n,m;
string str;

void init()
{
    for(int i=0;i<=n+1;i++)
    {
        f[i]=g[i]=dp[i]=0;
        q[i]={0,0};
    }
    vec.clear();
}

void solve()
{
    cin>>n>>m;
    init();
    fer(i,1,n)
    {
        cin>>a[i];
    }
    a[n+1]=0;a[0]=0;
    cin>>str;str=" "+str;
    int tt=-1,hh=0;
    q[++tt]={0,0};
    vec.push_back(0);
    for(int i=1;i<=n+1;i++)
    {
        while(hh<=tt&&(i-q[hh].Y)>m)hh++;
        f[i]=q[hh].X+a[i];
        while(hh<=tt&&q[tt].X>=f[i])tt--;
        if(str[i]=='1')
        {
            while(hh<=tt)tt--;
            vec.push_back(i);
        }
        q[++tt]={f[i],i};
    }
    vec.push_back(n+1);
    tt=-1,hh=0;
    q[++tt]={0,n+1};
    for(int i=n;i>=0;i--)
    {
        while(hh<=tt&&(q[hh].Y-i)>m)hh++;
        g[i]=q[hh].X+a[i];
        while(hh<=tt&&q[tt].X>=g[i])tt--;
        if(str[i]=='1')
        {
            while(hh<=tt)tt--;
        }
        q[++tt]={g[i],i};
    }
    tt=-1;hh=0;
    q[++tt]={0,0};
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt&&i-q[hh].Y>m)hh++;
        dp[i]=q[hh].X+g[i];
        while(hh<=tt&&q[tt].X>=f[i])tt--;
        if(str[i]=='1')
        {
            while(hh<=tt)tt--;
        }
        q[++tt]={f[i],i};
    }
    int op;
    cin>>op;
    while(op--)
    {
        int id,x;
        cin>>id>>x;
        int res=dp[id]-a[id]+x;
        if(str[id]=='1')
        {
            cout<<res<<endl;
            continue;
        }
        int mi=1e17;
        auto it= lower_bound(all(vec),id);
        int l=*(it-1);l=max(id-m+1,l);
        if(*it==id)it++;
        int r=*it;
        for(int i=l;i<id;i++)
        {
            if(i+m<=r)
                mi=min(mi,g[i+m]);
            res=min(res,f[i]+mi);
        }
        cout<<res<<endl;
    }
}

signed main()
{
    ac;
}