#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
//#define int long long
const int N = 5e5 + 50;
const int M = 5e5 + 5;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
//random_shuffle(id + 1, id + n + 1);
ll ksm(ll a, ll b);
ll gcd(ll a, ll b);

ll n, k, Q;
ll a[N];
string str;
ll dp[N] = { 0 };//表示在以第i个位置结尾的最小代价
ll b[N] = { 0 };//翻转求第i个位置选了的ans


void solve()
{
	//感觉就是个dp,但是这n,q有点太大了点，
	//对于每个q都用n的复杂度跑，感觉会t
	//但是之前，我们已经获取了一部分，(在更改的元素之前的序列)
	//那部分，我们是可以接着用的，每次我们从那个地方开始，能优化一下
	//试试
	//怎么还有位置是要必须建，等等还有这种好事
	//为1的位置相当于把整个数列进行了划分
	//到单点修改导致的决策影响仅能影响到下一个一的位置
	//在往后的决策都直接加上前置的决策即可

	//写的一坨，思路比较纯实现还不好，单调队列能维护出n的复杂度求
	//先改一发试试

	//改了发t的，然后我发现了题解的重点，g数组
	//我们发现单点修改的时候，

	priority_queue < pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > >q;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)cin >> a[i];
	cin >> str; str = "1" + str; str = str + "1"; a[n + 1] = 0; a[0] = 0;
	q.push({ 0,0 }); dp[0] = 0;
	for (int i = 1; i <= n+1; i++) {
		while (q.size() && i - q.top().Y > k)q.pop();
		dp[i] = q.top().X + a[i];
		if (str[i] == '1') {
			while (q.size())q.pop();
		}
		q.push({ dp[i],i });
	}
	while (q.size())q.pop();

	
	q.push({ 0,n+1 }); b[n+1] = 0;
	for (int i = n; i>=0; i--) {
		while (q.size() && q.top().Y - i > k)q.pop();
		b[i] = q.top().X + a[i];
		if (str[i] == '1') {
			while (q.size())q.pop();
		}
		q.push({ b[i],i });
	}
	while (q.size())q.pop();

	/*
	reverse(a + 1, a + n + 1);
	reverse(str.begin()+1, str.begin() + n + 1);

	q.push({ 0,0 }); b[0] = 0;
	for (int i = 1; i <= n + 1; i++) {
		while (q.size() && i - q.top().Y > k)q.pop();
		b[i] = q.top().X + a[i];
		if (str[i] == '1') {
			while (q.size())q.pop();
		}
		q.push({ b[i],i });
	}
	while (q.size())q.pop();

	reverse(a + 1, a + n + 1);
	reverse(str.begin() + 1, str.begin() + n + 1);
	reverse(b, b + n + 2);*/

	for (int i = 1; i <= n; i++) b[i] -= a[i];

	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		ll pos, val; cin >> pos >> val;
		//单点修改以后可怎么搞
		//总不能再跑完，试试，要不
		if (str[pos] == '1') {
			cout << dp[n + 1] + (-a[pos] + val) << endl; continue;
		}
		//有点想法，其实可以看做两种选择，一种是更新后选，一种不选
		//如果选，ans应为dp+b-a
		//如果不选呢，大于pos位置的很多元素有选pos的能力
		//
		//ll ans = dp[pos] + b[pos] - a[pos] * 1 + val;
		// << ans << endl;
		ll ans = maxm;
		for (int ii = max(0ll, pos - k); ii < pos; ii++) {
			if (str[ii] == '1') {
				while (q.size())q.pop();
			}
			q.push({ dp[ii],ii });
		}
		for (int ii = pos; ii <= min(n + 1, pos + k); ii++) {
			while (q.size() && ii - q.top().Y > k)q.pop();
			ll mid= q.top().X + a[ii];
			//cout << q.top().X << " " << q.top().Y << endl;
			if (str[ii] == '1') {
				while (q.size())q.pop();
			}
			q.push({ mid,ii });
			//cout << mid << " " << b[ii] << " " << ii << endl;
			mid += b[ii];
			ans = min(ans, mid);
		}
		cout << ans << endl;
		while (q.size())q.pop();
	}

	return;
}


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

/*PonyHex*/


ll ksm(ll a, ll b) {
	ll base = a;
	ll ans = 1;
	while (b) {
		if (b & 1)ans *= base % mod;
		ans %= mod;
		base *= base; base %= mod;
		b >>= 1;
	}
	return ans % mod;
}
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}