#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define per(i, a, b) for (int i = int(b)-1; i >= int(a); i--)
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vector<int>;
using pii = pair<int, int>;

template <class T, class F> struct sliding_aggregation {
	stack<T> as, bs, ae, be;
	F f;
	T one, vs, ve;
	sliding_aggregation(F f_, T one_) : f(f_), one(one_), vs(one), ve(one) {}

	void push_s(const T& x) {
		as.push(x), bs.push(vs = f(x, vs));
	}
	void push_e(const T& x) {
		ae.push(x), be.push(ve = f(ve, x));
	}
	void reduce() {
		while (!ae.empty()) {
			push_s(ae.top()), ae.pop();
		}
		while (!be.empty()) be.pop();
		ve = one;
	}

	bool empty() const {
		return as.empty() && ae.empty();
	}
	int size() const {
		return int(as.size() + ae.size());
	}

	void push(const T& x) {
		if (as.empty()) {
			push_s(x), reduce();
		} else {
			push_e(x);
		}
	}
	void pop() {
		assert(!empty());
		if (as.empty()) reduce();
		as.pop(), bs.pop();
		vs = (bs.empty() ? one : bs.top());
	}
	T query() const {
		return f(vs, ve);
	}
};

const ll INF = 1e17;

vector<ll> get_dp(int N, int K, const vector<ll>& A, const string& S) {
	assert(int(A.size()) == N+2), assert(int(S.size()) == N+2);
	vector<ll> dp(N+2);
	auto imin = [](const ll& x, const ll& y) -> ll {
		return min(x, y);
	};
	auto swag = sliding_aggregation(imin, INF);
	swag.push(0);
	for (int i = 1; i <= N+1; i++) {
		while (swag.size() > K) swag.pop();
		assert(!swag.empty());
		dp[i] = swag.query() + A[i];
		if (S[i] == '1') {
			while (!swag.empty()) swag.pop();
		}
		swag.push(dp[i]);
	}
	return dp;
}

void solve() {
	int N, K; cin >> N >> K;

	vector<ll> A(N+2);
	A[0] = A.back() = 0;
	for (int i = 1; i <= N; i++) cin >> A[i];

	string S; cin >> S;
	S.insert(S.begin(), '1'), S.push_back('1');
	
	auto fdp = get_dp(N, K, A, S);
	auto bdp = get_dp(N, K, vector<ll>(A.rbegin(), A.rend()), string(S.rbegin(), S.rend()));
	reverse(bdp.begin(), bdp.end());

	int Q; cin >> Q;
	vector<ll> rdp(K);
	while (Q--) {
		int p; ll v; cin >> p >> v;
		ll res = INF;
		if (S[p] == '1') {
			res = fdp.back() - A[p] + v;
		} else {
			res = (fdp[p] - A[p]) + v + (bdp[p] - A[p]);
			fill(rdp.begin(), rdp.end(), INF);
			for (int k = 1; k < K; k++) {
				rdp[k] = bdp[p+k];
				if (S[p+k] == '1') break;
			}
			ll pmin = INF;
			for (int k = 1; k < K; k++) {
				pmin = min(pmin, fdp[p-k]);
				res = min(res, pmin + rdp[K-k]);
				if (S[p-k] == '1') break;
			}
		}
		cout << res << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int T; cin >> T;
	while (T--) solve();

	return 0;
}