#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define i64 long long
#define int long long
#define endl '\n'
#define lb(x) ((x) & (-x))
using namespace std;
const i64 mod = 1e18;
const int maxn = 1e15;
signed main()
{
    IOS;
    int t; cin >> t;
    while(t--)
    {
        int n,k; cin >> n >> k;
        vector<int> a(n+2);
        for(int i = 1; i <= n; ++i) cin >> a[i];
        string s; cin >> s;
        s = " " + s;
        s.push_back('0');
        
        
        vector<int> per(n+2,mod);
        per[0] = 0;
        
        deque<int> q;
        q.push_back(0);
        
        for(int i = 1; i <= n+1; ++i)
        {
            while(q.size() && i - q.front() > k) q.pop_front();
            per[i] = per[q.front()] + a[i];
            while(q.size() && per[q.back()] >= per[i]) q.pop_back();
            if(s[i] == '1')
            {
                while(q.size()) q.pop_back();
            }
            q.push_back(i);
        }
        
        vector<int> suf(n+2,mod);
        suf[n+1] = 0;
        
        while(q.size()) q.pop_back();
        q.push_back(n+1);
        for(int i = n; i >= 0; --i)
        {
            while(q.size() && q.front() - i > k) q.pop_front();
            suf[i] = suf[q.front()] + a[i];
            while(q.size() && suf[q.back()] >= suf[i]) q.pop_back();
            if(s[i] == '1')
            {
                while(q.size()) q.pop_back();
            }
            q.push_back(i);
        }
        int op; cin >> op;
        while(op--)
        {
            int x,y; cin >> x >> y;
            
            
            deque<pair<int,int> > g;
            for(int i = max(0LL,x-k); i < x; ++i)
            {
                while(g.size() && g.front().first > per[i]) g.pop_front();
                
                if(s[i] == '1')
                {
                    while(g.size()) g.pop_back();
                }
                
                g.push_back({per[i],i});
            }
            
            int mx = mod;
            
            for(int i = x; i <= min(x+k,n+1); ++i)
            {
                while(g.size() && i - g.front().second > k) g.pop_front();
                int res = g.front().first;
                if(i == x) res += y;
                else res += a[i];
                mx = min(mx,res + suf[i] - a[i]);
                if(s[i] == '1')
                {
                    while(g.size()) g.pop_back();
                }
                g.push_back({res,i});
            }
            cout << mx << endl;
        }
    }
    return 0;

}