#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

bool isPrime(int x){
	if (x <= 1)
		return false;
	for (int i = 2; i * i <= x; ++i)
		if (x % i == 0)
			return false;
	return true;
}

int check(int x){
	if (x == 1)
		return 8;
	
	/* divisorts and amount */
	int cnt = 0, d[20][2], num = 1;
	int t = x;
	for (int i = 2; i * i <= t; ++i)
		if (t % i == 0){
			d[cnt][0] = i;
			d[cnt][1] = 0;
			for (; t % i == 0; t /= i)
				++d[cnt][1];
			num *= d[cnt][1] + 1;
			++cnt;
		}
	if (t > 1){
		d[cnt][0] = t;
		d[cnt][1] = 1;
		num <<= 1;
		++cnt;
	}

	/* sum of divisors */
	int sum = 0;
	int dd;
	for (dd = 1; dd * dd < x; ++dd)
		if (x % dd == 0)
			sum += dd + x / dd;
	if (dd * dd == x)
		sum += dd;

	/* product of divisors is a square number? */
	bool sqrFlag = true;
	for (int i = 0; sqrFlag && i < cnt; ++i){
		bool tmpFlag = false;
		for (int j = 0; j < cnt; ++j)
			if (i != j && d[j][1] & 1){
				tmpFlag = true;
				break;
			}
		tmpFlag |= d[i][1] * (d[i][1] + 1) / 2 % 2 == 0;
		sqrFlag &= tmpFlag;
	}

	return (cnt == 1 && d[0][1] == 1) | isPrime(num) << 1 | isPrime(sum) << 2 | sqrFlag << 3;
}

int n, K;
int cnt[16];
int w[4], value[16];

const int lst[16] = {15, 14, 13, 11, 7, 3, 5, 6, 9, 10, 12, 1, 2, 4, 8, 0};
const int cvalue[16] = {4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 0};

int main(){
	int cas;
	scanf("%d", &cas);
	while (cas--){
		scanf("%d%d", &n, &K);
		memset(cnt, 0, sizeof(cnt));
		for (int i = 0; i < n; ++i){
			int num, b;
			scanf("%d%d", &num, &b);
			int t = check(num);
			printf("%d%c", __builtin_popcount(t), i < n - 1 ? ' ' : '\n');
			cnt[t] += b;
		}

		memset(value, 0, sizeof(value));
		for (int i = 0; i < 4; ++i){
			scanf("%d", &w[i]);
			for (int j = 0; j < 16; ++j)
				if (!(j & (1 << i)))
					value[j] += w[i];
		}

		int zero = 0;
		for (int i = 15; i >= 0; --i)
			zero = zero << 1 | cnt[i] == 0;

		int ans = -(1 << 30);
		for (int tk, mask = (1 << 16) - 1; mask >= 0; --mask)
			if ((mask & zero) == 0 && (tk = K - __builtin_popcount(mask)) >= 0){
				int score = 0, lmask = 0;
				for (int i = 0; i < 16; ++i)
					if (mask & 1 << lst[i]){
						score += cvalue[i];
						lmask |= lst[i];
						int choose = min(tk, cnt[lst[i]] - 1);
						tk -= choose;
						score += choose * cvalue[i];
					}
				score += value[lmask];
				if (!tk)
					ans = max(ans, score);
			}
		printf("%d\n", ans);
	}
	return 0;
}