968. 食物

【题目描述】

辉夜原本是生活在月宫的月之公主。

辉夜从月都弄了很多吃的回到了幻想乡，有$n$种不同的食物，第$i$种食物的美味度为$t_i$，一份食物的大小为$u_i$，共有$v_i$份。但是麻烦的事情出现了，她要把这些食物运回永远亭，于是辉夜便弄来了$m$种运载工具。第$i$种运载工具可以运输大小总和不超过$x_i$的食物，运输一次的费用是$y_i$，总共可以运输$z_i$次。

辉夜打算选取一些食物运回永远亭，他们的美味度之和（每份食物的和，即使他们都是同一种食物）至少是$p$。值得注意的是，一份食物可以被拆成份分批次运输，送到永远亭后在组装起来。伯是如果不把一份食物完整的运过去，是无法得到美味度的。辉夜想知道最少需要花费的运输费用是多少。由于辉夜的预算仅有$50000$，因此如果费用超过这个数或者无法获得$p$的美味度，输出“TAT”。

【输入格式】

第一行一个数$T$，表示有$T$组数据。

对于每组数据，第一行有三个整数$n,m,p$。

接下来$n$行，每行三个整数$t,u,v$，描述一种食物。

最后$m$行，每行三个整数$x,y,z$，描述一种运载工具。

【输出格式】

对于每组数据，输出辉夜想知道的答案。注意存在无解的情况。

【样例输入】

4
1 1 7
14 2 1
1 2 2
1 1 10
10 10 1
5 7 2
5 3 34
1 4 1
9 4 2
5 3 3
1 3 3
5 3 2
3 4 5
6 7 5
5 3 8
1 1 1
1 2 1
1 1 1

【样例输出】

4
14
12
TAT

【数据规模与约定】

$T$不会很大。

对于$20\%$的数据，$n,m\leq 20$。

对于$50\%$的数据，$n,m\leq 30,t_i,u_i,v_i,x_i,y_i,z_i\leq 10$。

对于$100\%的数据，$n,m\leq 200, 0\leq p\leq 50000,1\leq t_i,u_i,v_i,x_i,y_i,z_i\leq 100$。