#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3fffFFFF;

struct node {
	int val, space, num;
}a[210], b[210];

int f[50110];
int g[50110];

void gao(int n, node a[], int f[], int V, int sign)
{
	for (int i = 1; i <= V; i++) f[i] = INF * sign;
	for (int i = 1; i <= n; i++) {
		int v = a[i].val;
		int c = a[i].num;
		int w = a[i].space;
		for (int d = 0; d < v; d++) {
			deque<PII> Q;
			for (int j = 0; j <= (V - d) / v; j++) {
				int now = f[j * v + d] - j * w;
				while (!Q.empty() && Q.back().first * sign >= now * sign) Q.pop_back();
				Q.push_back(PII(now, j));
				if (j - Q.front().second > c) Q.pop_front();
				f[j * v + d] = Q.front().first + j * w;
			}
		}
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, m, P;
		scanf("%d%d%d", &n, &m, &P);
		for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].val, &a[i].space, &a[i].num);
		for (int i = 1; i <= m; i++) scanf("%d%d%d", &b[i].space, &b[i].val, &b[i].num);	
		gao(n, a, f, P + 100, 1);
		gao(m, b, g, 50000, -1);
		int ans = INF;
		for (int i = P; i <= P + 100; i++) {
			ans = min(ans, f[i]);
		}
		int tag = 0;
		for (int i = 1; i <= 50000; i++) {
			if (g[i] >= ans) {
				printf("%d\n", i);
				tag = 1;
				break;
			}
		}
		if (!tag) puts("TAT");
	}
	return 0;
}