//from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 10;
int n, k;
int a[N];
string s;
int f[N], g[N], h[N];
int q;

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  int test; cin >> test;
  while (test--) {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    a[n + 1] = f[n + 1] = g[n + 1] = 0;
    cin >> s; s = '@' + s;
    deque<int> dq;
    dq.push_back(0);
    for (int i = 1; i <= n; ++i) {
      while (dq.size() && dq.back() < i - k) dq.pop_back();
      f[i] = f[dq.back()] + a[i];
      while (dq.size() && f[dq.front()] >= f[i]) dq.pop_front();
      if (s[i] == '1') dq.clear();
      dq.push_front(i);
    }
    dq.clear();
    dq.push_back(n + 1);
    for (int i = n; i >= 1; --i) {
      while (dq.size() && dq.back() > i + k) dq.pop_back();
      g[i] = g[dq.back()] + a[i];
      while (dq.size() && g[dq.front()] >= g[i]) dq.pop_front();
      if (s[i] == '1') dq.clear();
      dq.push_front(i);
    }

    cin >> q;
    while (q--) {
      int p, v; cin >> p >> v;
      int pre = a[p]; a[p] = v;
      for (int i = p; i <= min(n, p + k); ++i) h[i] = f[i];
      dq.clear();
      for (int i = max(0, p - k); i < p; ++i) {
        while (dq.size() && f[dq.front()] >= f[i]) dq.pop_front();
        if (s[i] == '1') dq.clear();
        dq.push_front(i);
      }
      for (int i = p; i <= min(n, p + k); ++i) {
        while (dq.size() && dq.back() < i - k) dq.pop_back();
        f[i] = f[dq.back()] + a[i];
        while (dq.size() && f[dq.front()] >= f[i]) dq.pop_front();
        if (s[i] == '1') dq.clear();
        dq.push_front(i);
      }
      int mi = 1e9;
      int it = dq.back();
      for (int i = it + 1; i <= min(n + 1, it + k); ++i) {
        mi = min(mi, g[i]);
        if (s[i] == '1') {
           mi = g[i];
          break;
        }
      }
      cout << f[it] + mi << "\n";
      for (int i = p; i <= min(n, p + k); ++i) f[i] = h[i];
    }


  }

}

answer.code: In function ‘int32_t main()’:
answer.code:53:23: error: no matching function for call to ‘max(int, long long int)’
   53 |       for (int i = max(0, p - k); i < p; ++i) {
      |                    ~~~^~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:53:23: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
   53 |       for (int i = max(0, p - k); i < p; ++i) {
      |                    ~~~^~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:53:23: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
   53 |       for (int i = max(0, p - k); i < p; ++i) {
      |                    ~~~^~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:53:23: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
   53 |       for (int i = max(0, p - k); i < p; ++i) {
      |                    ~~~^~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:53:23: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
   53 |       for (int i = max(0, p - k); i < p; ++i) {
      |                    ~~~^~~~~~~~~~
answer.code:19:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
answer.code:20:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   20 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~