OpenJudge

10:2018 ACM/ICPC in Peking University

总时间限制:
1000ms
内存限制:
65536kB
描述

The 2018 ACM/ICPC world final contest will take place in Peking University. As you know the competition will last for 5 hours and the contestant need to eat some desserts during the competition to provide energy. Xiaoming from school of EECS will prepare the dessert for the ACM contest. He wants to prepare different types of Chinese desserts such as mooncake, baozi, etc. Every type of desserts may provide different amounts of energy and they will take up different size of space.
Then, Xiaoming needs to pack the desserts. He will use boxes to pack the desserts. Different boxes may carry different amounts of desserts in size and have different costs. It is possible to split a single dessert into several parts and put them into different boxes, then assemble the parts at the game area. Note that a dessert does not provide any energy if some part of it is missing.

Xiaoming wants to know how much it would cost at least to provide desserts of a total energy of P (only the packing part cost money).


输入
The first line of input contains an integer T (T≤10) representing the number of test cases. For each test case there are three integers n, m, p on the first line (1≤n≤200,1≤m≤200,0≤p≤50000), representing the number of different desserts, the number of different boxes and the least energy required respectively.

In the following n lines, each line contains three integers ti, ui, vi, (1≤ti≤100,1≤ui≤100,1≤vi≤100) indicating that ith dessert can provide ti energy, takes up space of size ui and that Xiaoming can prepare at most vi of them.

On each of the next m lines, there are also three integers xj,yj,zj(1≤xj≤100,1≤yj≤100,1≤zj≤100) indicating that the jth box can carry at most size of xj space dessert, cost yj money and that Xiaoming can use at most zj of them.
输出
For every test case output the minimum cost to provide the dessert of enough energy in the game area if it is possible and its cost is no more than 50000. Otherwise, output FAIL on the line instead.
样例输入
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 
FAIL

01 Use "long long" to calculate the answer
05 Expected Value of an Expression: Ai is less than 2^20

全局题号
15303
提交次数
11
尝试人数
2
通过人数
0