#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>

using ll = long long;

const int N = 5e5 + 10;

int n, k, Q;
ll a[N];
ll pre[N], suf[N];
int q[N];
string s;

void solve()
{
	cin >> n >> k;
	for (int i = 1;i <= n;i++) cin >> a[i];
	a[n + 1] = 0;
	cin >> s;
	s = '1' + s + '1';

	int hh = 0, tt = -1;
	q[++tt] = 0;
	for (int i = 1;i <= n + 1;i++)
	{
		pre[i] = pre[q[hh]] + a[i];
		if (hh <= tt && i - k + 1 > q[hh]) hh++;
		while (hh <= tt && (pre[q[tt]] >= pre[i] || s[i] == '1')) tt--;
		q[++tt] = i;
	}

	hh = 0, tt = -1;
	q[++tt] = n + 1;
	for (int i = n;i > 0;i--)
	{
		suf[i] = suf[q[hh]] + a[i];
		if (hh <= tt && i + k - 1 < q[hh]) hh++;
		while (hh <= tt && (suf[q[tt]] >= suf[i] || s[i] == '1')) tt--;
		q[++tt] = i;
	}

	vector<ll> val(n + 2, 1e17);
	cin >> Q;
	while (Q--)
	{
		int x;
		ll v;
		cin >> x >> v;
		ll ans = pre[x] + suf[x] - 2 * a[x] + v;
		if (s[x] != '1')
		{
			val[x] = 1e17;
			int pos = x;
			for (int i = x - 1;x - i < k;i--)
			{
				val[i] = min(val[i + 1], pre[i]);
				pos = i;
				if (s[i] == '1') break;
			}
			for (int i = x + 1;i - x < k;i++)
			{
				ans = min(ans, suf[i] + val[max(pos, i - k)]);
				if (s[i] == '1') break;
			}
		}
		cout << ans << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}