///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG(a) cout<<a<<endl

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
	out << '(' << p.first << ", " << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
	for (T i : ve)
		out << i << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
	for (auto i : mp)
		out << i << '\n';
	return out;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"

const int mod = 998244353;
const int N = 1e6 + 10;

void solve(int CASE)
{
	ll n, k; cin >> n >> k;
	var a = vector<ll>(n + 2, 0);
	fa(i, 1, n)cin >> a[i];
	string s; cin >> s; s = '1' + s + '1';

	// 前 i 个距离的最小成本，第 i 个要选
	var pre = vector<ll>(n + 2, 0);
	var suf = vector<ll>(n + 2, 0);
	var Q = deque<ll>();

	// 计算前缀
	Q.pb(0);
	fa(i, 1, n) {
		var f = [&]()->void {
			while (i - Q.front() > k)
				Q.pop_front();

			pre[i] = pre[Q.front()] + a[i];

			// 维护 k 区间内 队头小，队尾大 的单调队列
			while (Q.size() and pre[Q.back()] > pre[i])
				Q.pop_back();

			Q.pb(i);
			};

		if (s[i] == '1') {
			f();
			while (Q.size())Q.pop_back();
			Q.pb(i);
		}
		else f();
	}
	ll ans = LINF;
	fb(i, n, n - k) {
		ans = min(ans, pre[i]);
		if (s[i] == '1')break;
	}
	while (Q.size())Q.pop_back();

	// 计算后缀
	Q.pb(n + 1);
	fb(i, n, 1) {
		var f = [&]()->void {
			while (Q.front() - i > k)
				Q.pop_front();

			suf[i] = suf[Q.front()] + a[i];

			// 维护 k 区间内 队头小，队尾大 的单调队列
			while (Q.size() and suf[Q.back()] > suf[i])
				Q.pop_back();

			Q.pb(i);
			};

		if (s[i] == '1') {
			f();
			while (Q.size())Q.pop_back();
			Q.pb(i);
		}
		else f();
	}

	ll q; cin >> q;
	fa(i, 1, q) {
		ll p, v; cin >> p >> v;
		ll lmn = LINF, rmn = LINF;
		if (s[p] == '1')
			cout << ans - a[p] + v << endl;
		else {
			ll l_1_pos = p, r_1_pos = p; // 左右最多能延申的位置

			// 1. 选了 p 点
			fb(i, p - 1, max(0ll, p - k)) {
				lmn = min(lmn, pre[i]);
				l_1_pos = i;
				if (s[i] == '1')break;
			}
			fa(i, p + 1, min(n + 1, p + k)) {
				rmn = min(rmn, suf[i]);
				r_1_pos = i;
				if (s[i] == '1')break;
			}
			var res = lmn + rmn + v;

			// 2. 不选 p 点，pre 在 p 前，suf 在 p 后，两者距离小于 k
			HashMap<int, ll>mn_pre; // 前缀 i 到 p - 1 的最小值
			ll last = LINF; // 上一个最小值
			fb(i, p - 1, l_1_pos) {
				mn_pre[i] = min(last, pre[i]);
				last = mn_pre[i];
			}
			fa(i, p + 1, r_1_pos) {
				if (i - k == p)break; // 不选 p 点
				var tmp = max(i - k, l_1_pos);
				//if (i - k < l_1_pos)continue; // 长度不合法
				res = min(res, suf[i] + mn_pre[tmp]);
			}

			cout << res << endl;
		}
	}
	return;
}

int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}