#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 INF = 1e18;

template<class Info>
struct SegmentTree
{
	int n;
	std::vector<Info> info;

	SegmentTree() : n(0) {}
	SegmentTree(int n_, Info v_ = Info())
	{
		init(n_, v_);
	}
	SegmentTree(std::vector<Info> init_)
	{
		init(init_);
	}
	void init(int n_, Info v_ = Info())
	{
		init(std::vector(n_, v_));
	}
	void init(std::vector<Info> init_)
	{
		n = init_.size();
		info.assign(4 << std::__lg(n), Info());
		std::function<void(int, int, int)> build = [&](int p, int l, int r)
		{
			if(r - l == 1)
			{
				info[p] = init_[l];
				return;
			}

			int mid = (l + r) >> 1;
			build(p << 1, l, mid);
			build(p << 1 | 1, mid, r);
			pull(p);
		};
		build(1, 0, n);
	}

	void pull(int p)
	{
		info[p] = info[p << 1] + info[p << 1 | 1];
	}

	void modify(int p, int l, int r, int x, const Info &v)
	{
		if(r - l == 1)
		{
			info[p] = v;
			return;
		}

		int mid = (l + r) >> 1;
		if(x < mid) modify(p << 1, l, mid, x, v);
		else modify(p << 1 | 1, mid, r, x, v);
		pull(p);
	}
	void modify(int p, const Info &v)
	{
		modify(1, 0, n, p, v);
	}

	Info rangeQuery(int p, int l, int r, int x, int y)
	{
		if(l >= y || r <= x) return Info();
		if(l >= x && r <= y) return info[p];

		int mid = (l + r) >> 1;
		return rangeQuery(p << 1, l, mid, x, y) + rangeQuery(p << 1 | 1, mid, r, x, y); 
	}
	Info rangeQuery(int l, int r)
	{
		return rangeQuery(1, 0, n, l, r);
	}
};

struct Info
{
	std::pair<i64, int> min = {INF, 0};
};

Info operator+(Info a, Info b)
{
	return {std::min(a.min, b.min)};
}

void solve()
{
	int n, k; std::cin >> n >> k;
	n += 2;
	std::vector<i64> a(n);
	for(int i = 1; i < n - 1; i++) std::cin >> a[i];

	std::string s; std::cin >> s;
	s = "1" + s + "1";

	int q; std::cin >> q;
	std::vector<std::vector<std::pair<int, int>>> val(n);
	std::vector<i64> ans(q, INF);
	for(int i = 0; i < q; i++)
	{
		int p, v; std::cin >> p >> v;
		val[p].emplace_back(v, i);
	}

	std::vector<Info> init(n);
	for(int i = 0; i < n; i++) init[i] = {std::make_pair(a[i], i)};
	SegmentTree<Info> segt(n);

	std::vector<Info> f(n);
	std::vector<int> pre(n);
	int lst = 0;
	for(int i = 1; i < n; i++)
	{
		pre[i] = lst;
		if(s[i] == '1') lst = i;
	}

	segt.modify(0, {std::make_pair(0, 0)});
	for(int i = 1; i < n; i++) 
	{
		f[i] = segt.rangeQuery(std::max(pre[i], i - k), i);
		f[i].min.first += a[i];
		segt.modify(i, {std::make_pair(f[i].min.first, i)});
	}
	std::vector<i64> g(a);

	int cur = n - 1, r = n - 1;
	while(cur)
	{
		int l = std::max(pre[cur], cur - k);
		// std::cerr << l << " " << r << " " << cur << "\n";
		for(int i = l; i < r; i++)
		{
			g[i] += g[cur];
			if(val[i].empty()) continue;
			for(auto [v, id] : val[i])
			{
				if(s[i] == '1')
				{
					ans[id] = f[n - 1].min.first - a[i] + v;
					continue;
				}
				segt.modify(i, {std::make_pair(f[i].min.first - a[i] + v, f[i].min.second)});
				for(int j = i + 1; j < r; j++)
				{
					f[j] = segt.rangeQuery(std::max(pre[j], j - k), j);
					f[j].min.first += a[j];
					segt.modify(j, {std::make_pair(f[j].min.first, j)});
				}

				ans[id] = std::min(ans[id], segt.rangeQuery(l, r).min.first + g[cur]);

				segt.modify(i, {std::make_pair(f[i].min.first - v + a[i], f[i].min.second)});
				for(int j = i + 1; j < r; j++)
				{
					f[j] = segt.rangeQuery(std::max(pre[j], j - k), j);
					f[j].min.first += a[j];
					segt.modify(j, {std::make_pair(f[j].min.first, j)});
				}
			}
		}
		cur = segt.rangeQuery(l, r).min.second;
		r = l;
	}

	// std::cerr << f[n - 1].min.first << "\n";
	for(auto i : ans) std::cout << i << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; std::cin >> t;
	while(t--) solve();

	return 0;
}

/*
1
19 6
285203460 203149294 175739375 211384407 323087820 336418462 114884618 61054702 243946442 19599175 51974474 285317523 222489944 26675167 300331960 1412281 324105264 33722550 169011266
1111111110110100011
2
3 127056246
10 63131453
*/