// Code by Heratino & Nelofus
// 消えたくって 羽ばたいて 今
// 消えたくなくなった
// 摘み取って残した ここでいつか 華咲かせる
// 消えたかった 私はもういない
// 消えなくてよかったな…
// だって君と出会い 芽吹いてしまった 運命の華
#include <bits/stdc++.h>
using i64 = long long;
using f64 = double;

//{{{
template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)	a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)	a = b;}
//}}}

constexpr int N = 5e5 + 10;
int n, k;
int a[N];
std::string s;
i64 f[N], g[N];
i64 sav1[N], sav2[N];

void solve() {
	std::cin >> n >> k;
	for (int i = 1; i <= n; i++)
		std::cin >> a[i];
	std::cin >> s;
	s = ' ' + s + ' ';
	std::deque<int> q1, q2;
	q1.push_back(0);
	for (int i = 1; i <= n; i++) {
		if (i - q1.front() > k)
			q1.pop_front();
		f[i] = f[q1.front()] + a[i];
		if (s[i] == '1')	while(!q1.empty())	q1.pop_back();
		while (!q1.empty() && f[q1.back()] > f[i])
			q1.pop_back();
		q1.push_back(i);
	}
	q2.push_back(n + 1);
	for (int i = n; i >= 1; i--) {
		if (q2.front() - i > k)
			q2.pop_front();
		g[i] = g[q2.front()] + a[i];
		if (s[i] == '1')	while (!q2.empty())	q2.pop_back();
		while (!q2.empty() && g[q2.back()] > g[i])
			q2.pop_back();
		q2.push_back(i);
	}

	for (int i = 1; i <= n; i++)
		sav1[i] = f[i], sav2[i] = g[i];
	int q;
	std::cin >> q;
	for (int _ = 1; _ <= q; _++) {
		int p, v, t;
		std::cin >> p >> v;
		t = a[p], a[p] = v;
		int l = std::max(p - k, 0);
		int r = std::min(p + k, n + 1);

		std::deque<int> q1, q2;
		for (int i = l; i <= r; i++) {
			if (i - q1.front() > k)
				q1.pop_front();
			if (i >= p)
				f[i] = f[q1.front()] + a[i];
			if (s[i] == '1')	while(!q1.empty())	q1.pop_back();
			while (!q1.empty() && f[q1.back()] > f[i])
				q1.pop_back();
			q1.push_back(i);
		}
		for (int i = r; i >= l; i--) {
			if (q2.front() - i > k)
				q2.pop_front();
			if (i <= p)
				g[i] = g[q2.front()] + a[i];
			if (s[i] == '1')	while (!q2.empty())	q2.pop_back();
			while (!q2.empty() && g[q2.back()] > g[i])
				q2.pop_back();
			q2.push_back(i);
		}

		i64 ans = 1e18;
		for (int i = l; i <= r; i++)
			chkmin(ans, f[i] + g[i] - a[i]), f[i] = sav1[i], g[i] = sav2[i];
		std::cout << ans << '\n';
		a[p] = t;
	}

	memset(f, 0, (n + 2) * sizeof(i64));
	memset(g, 0, (n + 2) * sizeof(i64));
	memset(a, 0, (n + 1) * sizeof(int));
	memset(sav1, 0, (n + 2) * sizeof(i64));
	memset(sav2, 0, (n + 2) * sizeof(i64));
}

int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}