#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

int a[220],b[220],c[220];
int f[80000],g[60000];
vector<PII> v;
int n,m,p;

int main(){
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&n,&m,&p);
		v.clear();
		for (int i=1;i<=n;i++){
			scanf("%d%d%d",&a[i],&b[i],&c[i]);
			int x=1;
			while (c[i]>=x){
				v.push_back(PII(a[i]*x,b[i]*x));
				c[i]-=x;
		//		cout << x<<" ";
				x*=2;
				
			}
			if (c[i]) v.push_back(PII(a[i]*c[i],b[i]*c[i]));
		//	cout << c[i]<<endl;
		}

		memset(f,-1,sizeof(f));
		f[0]=0;
		for (int i=0;i<v.size();i++){
			int y=v[i].first;
			int x=v[i].second;
			for (int j=p+y;j>=y;j--){
				if (f[j-y]>=0){
					if (f[j]==-1) f[j]=x+f[j-y];
						else f[j]=min(f[j],x+f[j-y]);
				}
			}
		}

	//	for (int i=0;i<=50;i++)
	//		if (f[i]>-1) printf("%d %d\n",i,f[i]);
		
		v.clear();
		for (int i=1;i<=m;i++){
			scanf("%d%d%d",&a[i],&b[i],&c[i]);
			int x=1;
			while (c[i]>=x){
				v.push_back(PII(a[i]*x,b[i]*x));
				c[i]-=x;
				//cout << x<<" ";
				x*=2;
			}
			if (c[i]) v.push_back(PII(a[i]*c[i],b[i]*c[i]));
			//cout << c[i]<<endl;
		}

		memset(g,0,sizeof(g));
		for (int i=0;i<v.size();i++){
			int x=v[i].first;
			int y=v[i].second;
			for (int j=50000;j>=y;j--){
				g[j]=max(g[j],x+g[j-y]);
			}
		}
		
		int ans=-1;
		for (int i=p;i<80000;i++)
			if (f[i]>-1){
				if (ans==-1) ans=f[i];
					else ans=min(ans,f[i]);
			}
		int tot=-1;
	//	for (int i=0;i<=100;i++)
	//		if (g[i]) printf("%d %d\n",i,g[i]);
		for (int i=0;i<=50000;i++)
			if (g[i]>=ans){tot=i;break;}

//		cout <<"!"<<ans<<"!"<<tot<<endl;
		
		if (ans==-1 || tot==-1 ) puts("TAT");
			else printf("%d\n",tot);

	}
	return 0;
}