//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], j[N];
int q;

void harm() {
  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);
  }

}

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;
    harm();

    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];
      for (int i = min(n, p + k); i >= p; --i) j[i] = g[i];

      deque<int> dq; dq.push_back(min(n + 1, p + k + 1));
      for (int i = min(n, p + k); i >= max(0ll, p - k - 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);
      }
      dq.clear();

      for (int i = max(0ll, p - k - 1); 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 answer = 1e15;
      while (dq.size()) {
        int it = dq.back(), mi = 1e15;
        for (int i = it + 1; i <= min(n + 1, it + k + 1); ++i) {
          mi = min(mi, g[i]);
          if (s[i] == '1') break;
        }
        answer = min(answer, f[it] + mi);
        dq.pop_back();
      }
      cout << answer << "\n";
      for (int i = p; i <= min(n, p + k); ++i) f[i] = h[i];
      for (int i = min(n, p + k); i >= max(0ll, p - k - 1); --i) g[i] = j[i];
      a[p] = pre;
    }
  }
}