#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=5e5+5; const ll inf=1e18;
char s[N];
int n,k,a[N],pre[N],suf[N];
ll dp1[N],dp2[N],res[N],pre2[N];
int q[N];
void wk(int l,int r){
    dp1[l]=dp1[r]=dp2[l]=dp2[r]=0;
    int L=1,R=0; q[++R]=l;
    rep(i,l+1,r){
        while(L<=R && q[L]<i-k)++L;
        assert(L<=R);
        // if(i==r){
        //     rep(j,L,R)cout<<q[j]<<' '; cout<<"###\n";
        // }
        dp1[i]=a[i]+dp1[q[L]];
        while(R>=L && dp1[q[R]]>=dp1[i])--R;
        
        q[++R]=i;
    }
    res[l]=dp1[r]-a[r];
    dp1[l]=dp1[r]=dp2[l]=dp2[r]=0;
    L=1,R=0; q[++R]=r;
    per(i,r-1,l){
        while(L<=R && q[L]>i+k)++L;
        assert(L<=R);
        dp2[i]=a[i]+dp2[q[L]];
        while(R>=L && dp2[q[R]]>=dp2[i])--R;
        q[++R]=i;
    }
    dp1[l]=dp1[r]=dp2[l]=dp2[r]=0;
}
void slv(){
    cin>>n>>k;
    rep(i,1,n)cin>>a[i];
    a[0]=a[n+1]=0;
    cin>>s+1;
    rep(i,1,n)s[i]-='0';
    s[0]=s[n+1]=1;
    rep(i,0,n+1){
        if(s[i]){
            pre[i]=i;suf[i]=i;
        }
        else pre[i]=pre[i-1];
    }
    per(i,n+1,0){
        if(!s[i])suf[i]=suf[i+1];
    }
    ll sum=0;
    rep(i,0,n){
        if(s[i])wk(i,suf[i+1]),sum+=res[i]; //cout<<res[i]<<'\n';
    }
    rep(i,1,n){
        if(s[i])sum+=a[i];
    }
    // rep(i,0,n+1)cout<<dp1[i]<<' '; cout<<'\n';
    // rep(i,0,n+1)cout<<dp2[i]<<" "; cout<<'\n';
    int Q;cin>>Q;
    while(Q--){
        int x,v;cin>>x>>v;
        ll w=0;
        if(s[x]){
            // cout<<sum<<' '<<v<<' '<<a[x]<<'\n';
            w=sum+v-a[x];
        }
        else{
            int lx=pre[x],rx=suf[x];
            ll w1=inf;
            rep(i,max(lx,x-k),x-1)w1=min(w1,dp1[i]);
            w+=w1; w1=inf;
            per(i,min(rx,x+k),x+1)w1=min(w1,dp2[i]);
            w+=w1+v; w1=inf;
            pre2[x+1]=dp2[x+1]; rep(i,x+2,min(rx,x+k))pre2[i]=min(pre2[i-1],dp2[i]);
            rep(i,max(lx,x-k+1),x-1){
                // cout<<i<<' '<<dp1[i]<<' '<<pre2[min(rx,i+k)]<<'\n';
                w1=min(w1,dp1[i]+pre2[min(rx,i+k)]);
            }
            // cout<<w1<<'\n';
            w=min(w,w1);
            w=sum-res[lx]+w;
        }
        cout<<w<<'\n';
    }
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}
/*
1
10 3
5 10 7 100 4 3 12 5 100 1
0001000010
2
2 3
6 15

5 6
1 1 1 1 1
00100
1
3 100
*/

answer.code: In function ‘void slv()’:
answer.code:44:8: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘char*’)
   44 |     cin>>s+1;
      |     ~~~^~~~~
      |     |     |
      |     |     char*
      |     std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:168:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  168 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:168:7: note:   conversion of argument 1 would be ill-formed:
answer.code:44:11: error: cannot bind non-const lvalue reference of type ‘bool&’ to a value of type ‘char*’
   44 |     cin>>s+1;
      |          ~^~
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:172:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  172 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/11/istream:172:7: note:   conversion of argument 1 would be ill-formed:
answer.code:44:11: error: invalid conversion from ‘char*’ to ‘short int’ [-fpermissive]
   44 |     cin>>s+1;
      |          ~^~
      |           |
      |           char*
answer.code:44:11: error: cannot bind rvalue ‘(short int)(((char*)(& s)) + 1)’ to ‘short int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:175:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  175 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:175:7: note:   conversion of argument 1 would be ill-formed:
answer.code:44:11: error: invalid conversion from ‘char*’ to ‘short unsigned int’ [-fpermissive]
   44 |     cin>>s+1;
      |          ~^~
      |           |
      |           char*
answer.code:44:11: error: cannot bind rvalue ‘(short unsigned int)(((char*)(& s)) + 1)’ to ‘short unsigned int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:179:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  179 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/11/istream:179:7: note:   conversion of argument 1 would be ill-formed:
answer.code:44:11: error: invalid conversion from ‘char*’ to ‘int’ [-fpermissive]
   44 |     cin>>s+1;
      |          ~^~
      |           |
      |           char*
answer.code:44:11: error: cannot bind rvalue ‘(int)(((char*)(& s)) + 1)’ to ‘int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:182:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  182 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:182:7: note:   conversion of argument 1 would be ill-formed:
answer.code:44:11: error: invalid conversion from ‘char*’ to ‘unsigned int’ [-fpermissive]
   44 |     cin>>s+1;
      |          ~^~
      |           |
      |           char*
answer.cod...