题目大意：

有$n$n种食物，每种食物可以提供美味度$t_i$ti​，大小为$u_i$ui​，有$v_i$vi​份。
有$m$m种运输工具，每种运输工具每次可以大小总和运输$≤x_i$≤xi​的食物，单次花费$y_i$yi​，可以使用$z_i$zi​次。
希望运输的食物的美味度总和$≥p$≥p，且能提供的使用费用最大值为$50000$50000，一份食物可以分成多块运输但是如果运输的不完整则不计美味度。
如果能够使美味度总和$≥p$≥p，且花费$≤50000$≤50000，则求出最小花费，否则输出$TAT$TAT

$1≤n,m≤200,0≤p≤50000,1≤t_i,u_i,v_i,x_i,y_i,z_i≤100$1≤n,m≤200,0≤p≤50000,1≤ti​,ui​,vi​,xi​,yi​,zi​≤100

分析：

令$S$S为美味度总和$≥p$≥p时最小的食物大小总和，
则我们令$dp_i$dpi​表示美味度总和为$i$i时，最小的食物大小总和，然后通过多重背包求得
注意$i$i的上界最大应该为$p+max(t_{[]})$p+max(t[]​)
然后在$S=min(dp_{i})$S=min(dpi​) $i∈[p,p+max(t_{[]})]$i∈[p,p+max(t[]​)]
然后我们发现，因为可以分成多块运输，
问题就可以转化成在使得运输的总大小$≥S$≥S时所需要的最小费用，
那我们可以设$g_i$gi​表示使用大小为$i$i时的最小花费，因为$S$S可能非常大，所以我们可以交换一下位置，
令$g_i$gi​表示花费$i$i的时候，所能得到的最大使用大小，那我们只需要求一个最小的费用$i$i满足最大使用大小$≥S$≥S，$i$i的上界为费用使用最大值$50000$50000，
那我们就可以也用多重背包来求解
因为这样的多重背包时间会很难受，所以我们可以通过二进制来进行优化
然后我们发现还是卡不过，可能需要单调队列的优化，
然后发现了有个可以水过的方法，
对于后者，我们令$c_{i,j}$ci,j​表示选到了第$i$i种运输方式，花费了$j$j时所能得到的最大使用大小，然后如果当前$c_{i,j}≥S$ci,j​≥S，那么我们对于接下来的$c_{i,j+1},..c_{i,50000}$ci,j+1​,..ci,50000​就可以剪枝掉。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>

#define N 205
#define M 50005
#define inf 0x3f3f3f3f

using namespace std;

struct Node { int t, u, v; }a[N];
struct Code { int x, y, z; }b[N];
struct Oier { int num, rv; }c[N*10];
struct Lier { int cost, v; }d[N*10];
int dp[N+M], g[N][M], n, m, p, T, cnt, tot;

void read(int &x)
{
	int f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9')   { if (s == '-')   f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + (s - '0'); s = getchar(); }
	x = x * f;
}

int main()
{
	read(T);
	while (T--)
	{
        read(n); read(m); read(p);
        for (int i = 1; i <= p + 100; i++) dp[i] = inf; dp[0] = 0;
        cnt = 0;
		for (int i = 1; i <= n; i++) 
		{
		    read(a[i].t), read(a[i].u), read(a[i].v);
			for (int j = 1; j <= a[i].v; j <<= 1) 
                a[i].v -= j, c[++cnt].rv = a[i].u * j, c[cnt].num = a[i].t * j;
            if (a[i].v) c[++cnt].rv = a[i].u * a[i].v, c[cnt].num = a[i].t * a[i].v; 
		}
		for (int i = 1; i <= cnt; i++)
		    for (int j = p + 100; j >= c[i].num; j--) dp[j] = min(dp[j], dp[j - c[i].num] + c[i].rv);
	    int cdp = inf;
		for (int i = p; i <= p + 100; i++) cdp = min(cdp, dp[i]);
	
	    for (int i = 1; i <= m; i++) 
	        for (int j = 1; j <= 50000; j++) g[i][j] = 0;
	    tot = 0; 
		for (int i = 1; i <= m; i++) read(b[i].x), read(b[i].y), read(b[i].z);
	
		if (cdp == inf) 
	    {
	    	printf("TAT\n");
			 continue;
		}
		int check = inf;
	    for (int i = 1; i <= m; i++)
	        for (int j = 0; j <= b[i].z; j++)
	            for (int k = 1; k <= min(check, 50000); k++)
	                if (k >= b[i].y * j)
	                {
	                	g[i][k] = max(g[i][k], g[i - 1][k - b[i].y * j] + b[i].x * j); 
					    if (g[i][k] >= cdp) 
					    {
					        check = min(check, k);
					        break;
						}
					}   
		if (check == inf) printf("TAT\n"); else printf("%d\n", check);
	}
	return 0;
}