#include <bits/stdc++.h>

#include <climits>
#include <cstdint>

using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")

using ui = unsigned int;
using ll = long long;
using ull = uint64_t;
using ld = long double;

template <typename K, typename V>
using umap = unordered_map<K, V>;

#define null NULL
#define len(a) static_cast<int>((a).size())
#define present(c, x) (c.find(x) != c.end())
#define inrange(val, start, end) (val >= start && val <= end)
const double PI = 2 * acos(0.0);

constexpr int iinf = 0x3f3f3f3f;
constexpr ll inf = 1'000'000'000'000'000;
constexpr ll mod = 1e9 + 7;

#define var(args...)                       \
  {                                        \
    string _s = #args;                     \
    stringstream _ss;                      \
    string ccurr = "";                     \
    for (int zz = 0; zz < len(_s); zz++) { \
      if (_s[zz] == ' ') continue;         \
      if (_s[zz] == ',') {                 \
        _ss << ' ' + ccurr;                \
        ccurr = "";                        \
      } else {                             \
        ccurr += _s[zz];                   \
      }                                    \
    }                                      \
    _ss << ' ' + ccurr;                    \
    istream_iterator<string> _it(_ss);     \
    vars(_it, args);                       \
  }
#define debugDecimal(d) cerr << setprecision(d) << fixed

void vars(istream_iterator<string> it) { cerr << '\n'; }
template <typename T, typename... Args>
void vars(istream_iterator<string> it, T a, Args... args) {
  cerr << " [" << *it << ": " << a << "] ";
  vars(++it, args...);
}

#define printVerdict(verdict) cout << (verdict ? "YES" : "NO") << '\n'
#define printDecimal(d) cout << setprecision(d) << fixed
#define printCase(_) cout << "Case #" << (_) << ": "

template <int I, typename TupleT>
ostream& printTupleImpl(ostream& out, const TupleT& t) {
  if constexpr (I < tuple_size_v<TupleT>) {
    out << get<I>(t) << " ";
    printTupleImpl<I + 1, TupleT>(out, t);
  }
  return out;
}
template <typename... Ts>
ostream& operator<<(ostream& out, const tuple<Ts...>& t) {
  return printTupleImpl<0>(out, t);
}

template <int I, typename TupleT>
istream& readTupleImpl(istream& in, TupleT* t) {
  if constexpr (I < tuple_size_v<TupleT>) {
    in >> get<I>(*t);
    readTupleImpl<I + 1, TupleT>(in, t);
  }
  return in;
}

template <typename... Ts>
istream& operator>>(istream& in, tuple<Ts...>& t) {
  return readTupleImpl<0>(in, &t);
}

template <typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
  return out << p.first << " " << p.second;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
  for (const T& a : arr) out << a << " ";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<vector<T>>& grid) {
  for (const vector<T>& row : grid) out << row << '\n';
  return out;
}
template <typename T>
istream& operator>>(istream& in, vector<T>& arr) {
  for (T& a : arr) in >> a;
  return in;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& a) {
  in >> a.first >> a.second;
  return in;
}

template <typename Fun>
class y_combinator_result {
  Fun fun_;

 public:
  template <typename T>
  explicit y_combinator_result(T&& fun) : fun_{std::forward<T>(fun)} {}

  template <typename... ArgTs>
  decltype(auto) operator()(ArgTs&&... args) {
    return fun_(std::ref(*this), std::forward<ArgTs>(args)...);
  }
};

template <typename Fun>
decltype(auto) y_combinator(Fun&& fun) {
  return y_combinator_result<decay_t<Fun>>(std::forward<Fun>(fun));
}

template <typename T>
struct Tree {
  // static constexpr T unit = make_pair(LLONG_MAX, -1);
  T f(T a, T b) { return min(a, b); }
  T unit;
  vector<T> s;
  int n;
  explicit Tree(int n_ = 0, T def = T{}) : unit(def), s(2 * n_, def), n(n_) {}
  void update(int pos, T val) {
    for (s[pos += n] = val; pos /= 2;) {
      s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
  }
  T query(int b, int e) {
    T ra = unit, rb = unit;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) ra = f(ra, s[b++]);
      if (e % 2) rb = f(s[--e], rb);
    }
    return f(ra, rb);
  }
};

inline void prayGod() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    cin >> a;
    a.insert(a.begin(), 0);
    a.push_back(0);
    string s;
    cin >> s;
    s = "1" + s + "1";
    n = len(s);
    vector<int> lb(n, 0), rb(n, n - 1);
    vector<ll> left(n), right(n);
    Tree<pair<ll, int>> rtree(n, make_pair(LLONG_MAX, -1)),
        ltree(n, make_pair(LLONG_MAX, -1));
    int boundary = 0;
    ltree.update(0, make_pair(0, 0));
    rtree.update(n - 1, make_pair(0, n - 1));
    vector<int> parent(n, -1);
    for (int i = 1; i < n; i++) {
      lb[i] = max({0, i - k, boundary});
      if (s[i] == '1') boundary = i;
      int par;
      tie(left[i], par) = ltree.query(lb[i], i);
      left[i] += a[i];
      parent[i] = par;
      ltree.update(i, make_pair(left[i], i));
    }
    boundary = n - 1;
    for (int i = n - 2; i >= 0; i--) {
      rb[i] = min({n - 1, i + k, boundary});
      if (s[i] == '1') boundary = i;
      right[i] = rtree.query(i + 1, rb[i] + 1).first + a[i];
      rtree.update(i, make_pair(right[i], i));
    }
    set<int> path;
    ll best_path = 0;
    {
      int curr = n - 1;
      while (curr != -1) {
        path.insert(curr);
        best_path += a[curr];
        curr = parent[curr];
      }
    }
    int q;
    cin >> q;
    Tree<ll> temp_tree(n, LLONG_MAX);
    while (q--) {
      int p, v;
      cin >> p >> v;
      if (present(path, p)) {
        // p is on optimal path
        ll ret = best_path - a[p] + v;
        for (int i = p + 1; i <= rb[p]; i++) {
          temp_tree.update(i, right[i]);
        }
        for (int i = p - 1; i >= lb[p]; i--) {
          // do stuff
          ll curr = temp_tree.query(i + 1, rb[i] + 1);
          if (curr != LLONG_MAX) curr += left[i];
          ret = min(ret, curr);
          temp_tree.update(i, curr);
        }
        for (int i = p - 1; i >= lb[p]; i--) {
          temp_tree.update(i, left[i]);
        }
        for (int i = p + 1; i <= rb[p]; i++) {
          // do stuff
          auto curr = temp_tree.query(lb[i], i);
          if (curr != LLONG_MAX) curr += right[i];
          ret = min(ret, curr);
          temp_tree.update(i, curr);
        }
        for (int i = lb[p]; i <= rb[p]; i++) {
          temp_tree.update(i, LLONG_MAX);
        }
        cout << ret << '\n';
      } else {
        ll ret = best_path;
        ll left_side = ltree.query(lb[p], p).first;
        ll right_side = rtree.query(p + 1, rb[p]).first;
        for (int i = lb[p]; i < p; i++) {
          ret = min(ret, left[i] + v + right_side);
        }
        for (int i = p + 1; i <= rb[p]; i++) {
          ret = min(ret, right[i] + v + left_side);
        }
        cout << ret << '\n';
      }
    }
  }
}

int main() {
#ifdef LLOCAL
  clock_t start = clock();
#endif
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);

  prayGod();
#ifdef LLOCAL
  clock_t end = clock();

  double time_taken = double(end - start) / CLOCKS_PER_SEC;
  debugDecimal(5) << time_taken << " s" << '\n';
#endif
}