#include <bits/stdc++.h>

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

int n, k;
int a[N];
string op;
int query;
int f[N], g[N], tmp[N];



void solve(){

	cin >> n >> k;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	a[0] = 0, a[n + 1] = 0, tmp[0] = 0, tmp[n + 1] = 0;
	int q[n + 10] = {0};	
	cin >> op;
	op = " " + op;
	
	int hh = 0, tt = -1;
	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];
		tmp[i] = 0;
	}	
	
	hh = 0, tt = -1;
	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 ++) g[i] -= a[i];
	
	
	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){
			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];	
		}
		
		int ans = 1e18;
		for (int i = x; i < x + k && i <= n + 1; i ++){
			if (tt >= hh && i - k > q[hh]) hh ++;
			tmp[i] = tmp[q[hh]] + a[i];	
			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;
			
		}
		
		cout << ans << endl;
		a[x] = old;
	}
	
	for (int i = 1; i <= n; i ++) f[i] = g[i] = 0;
	

}

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