辉夜从月都弄了很多吃的回到了幻想乡，有\(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\)。