#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N= 5e5 + 10;
const int INF = 1e18;
typedef pair<int,int> PII;
int n,m,K,a[N];
string s;
int f[N],g[N],h[N];


int dp(int x,int y)
{
	int old = a[x];
	a[x] = y;
	
	deque<PII> d;
	int L = max(1ll,x - K);
	int R = max(1ll,x - 1);
	if(x - K <= 0) d.push_back({0,0});
	for(int i=L; i<=R; i++)
	{
		if(s[i - 1] == '1') d.clear();
		while(d.size() && d.back().first >= f[i]) d.pop_back();
		d.push_back({f[i],i});
	}
	int res = INF;
	for(int i=x; i<x + K && i <= n + 1; i++)
	{
		while(d.front().second < i - K) d.pop_front();
		h[i] = d.front().first + a[i];
		res = min(res, h[i] + g[i]);
		if(s[i - 1] == '1') d.clear();
		while(d.size() && d.back().first >= h[i]) d.pop_back();
		d.push_back({h[i],i});
	}
	a[x] = old;
	return res;
}

void solve(){
	cin >> n >> K;
	for(int i=1; i<=n; i++) cin >> a[i];
	a[n + 1] = 0;
	g[n + 1] = 0;
	cin >> s;
	s = s + "1";
	deque<PII> d;
	d.push_back({0,0});
	for(int i=1; i<=n + 1; i++){
		while(d.front().second < i - K) d.pop_front();
		f[i] = d.front().first + a[i];
		if(s[i - 1] == '1') d.clear();
		while(d.size() && d.back().first >= f[i]) d.pop_back();
		d.push_back({f[i],i});
	}
	d.clear();
	d.push_back({0,n+1});
	for(int i=n; i>=1; i--){
		while(d.front().second > i + K) d.pop_front();
		g[i] = d.front().first + a[i];
		if(s[i - 1] == '1') d.clear();
		while(d.size() && d.back().first >= g[i]) d.pop_back();
		d.push_back({g[i],i});
	}
	for(int i=1; i<=n + 1; i++) g[i] -= a[i];
	int q;
	cin >> q;
	while(q--)
	{
		int x,y;
		cin >> x >> y;
		cout << dp(x,y) << endl;
	}
	
}

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