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

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

输入格式

第一行一个数$test$，表示有$test$组数据。
对于每组数据，第一行有三个整数$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

数据规模

test不会很大。
对于前20%的数据，$n,m≤20$。
对于前50%的数据，$n,m≤30，t_i,u_i​,v_i,x_i,y_i,z_i≤10$。
对于100%的数据，$1≤n,m≤200，0≤p≤50000，1≤t_i​,u_i,v_i​,x_i​,y_i,z_i≤100$。