#include <bits/stdc++.h>

#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 5e5 + 10;

int n, k;
int a[N];
string op;
int query;
int p[3010], v[3030];
int f[N], g[N], tmp[N];



void solve(){
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	cin >> op;
	op = " " + op;
	
	int hh = 0, tt = -1;
	int q[n + 3];
	q[0]=0;
	
	int s = 0;
	
	for (int i = 1; i <= n; i ++){
		if (tt >= hh && i - k > q[hh]) hh ++;
		
		if (i <= k) f[i] = s + a[i];
		else f[i] = f[q[hh]] + a[i];		
		if (op[i] == '1') hh = 0, tt = -1;	
		while (tt >= hh && f[i] < f[q[tt]]) tt --;
		q[++ tt] = i;
		if (i <= k && op[i] == '1') s += a[i];
	}	
	
	hh = 0, tt = -1;
	q[0] = 0;
	s = 0;
	
	for (int i = n; i >= 1; i --){
		if (tt >= hh && i + k < q[hh]) hh ++;
		if (i >= n - k + 1) g[i] = s + a[i];
		else g[i] = g[q[hh]] + a[i];
		if (op[i] == '1') hh = 0, tt = -1;
		while (tt >= hh && g[i] < g[q[tt]]) tt --;
		q[++ tt] = i;
		if (i >= n - k + 1 && op[i] == '1') s += a[i];
		
	}
	
//	for (int i = 1; i <= n; i ++) cout << g[i] << " \n"[i == n];
	
	for (int i = 1; i <= n; i ++) g[i] -= a[i];
//	for (int i = 1; i <= n; i ++) cout << a[i] << " \n"[i == n];
	
//	for (int i = 1; i <= n; i ++) cout << f[i] << " \n"[i == n];
//	for (int i = 1; i <= n; i ++) cout << g[i] << " \n"[i == n];
//	
	a[0] = 0, a[n + 1] = 0;
	
	cin >> query;
	
	hh = 0, tt = -1;
	while (query --){
		int x, val;
		cin >> x >> val;
		int old = a[x];
		a[x] = val;
		
//		for (int i = k; i > 0; i --) if (x - i >= 0){
//			tmp[i] = f[i];
//			
//		}
		
		
		for (int i = k; i > 0; i --) if (x - i >= 0){
			if (op[x - i] == '1') hh = 0, tt = -1;
			while (tt >= hh && f[q[tt]] >= f[x - i]) tt --;
			q[++ tt] = x - i;
			tmp[x - i] = f[x - i];
//			cout << tt << ' ' << f[q[hh] << endl;
			
		}
		
//		for (int i = hh; i <= tt; i ++) cout << q[i] << ' ' << tmp[q[i]] << endl;
		
		int ans = INF;
		for (int i = x; i < x + k && i <= n + 1; i ++){
//			if (i == x) cout << q[hh] << endl;
			
			if (tt >= hh && i - k > q[hh]) hh ++;
//			if (i == 4) cout << q[hh] << endl;
			
			tmp[i] = tmp[q[hh]] + a[i];	//if (i == 4) cout << tmp[q[hh]] << endl;
			
//			cout << q[hh] << ' ' << tmp[q[hh]] << ' ' << tmp[q[tt]] << ' ' <<  hh << ' ' << tt << endl;
			
			ans = min(ans, tmp[i] + g[i]);
		
			if (op[i] == '1') hh = 0, tt = -1;
			while (tt >= hh && tmp[i] <= tmp[q[tt]]) tt --;
			q[++ tt] = i;
			
		}
//		
		for (int i = x; i < x + k && i <= n + 1; i ++){
//			cout << tmp[i] << endl;
//			
		}
		
		cout << ans << endl;
		a[x] = old;
//		
//		cout << "----------------=======================-----------------------\n";
		
	}

}

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