OpenJudge

10:ACM/ICPC 2018

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

2018ACM/ICPC世界总决赛将在北京大学举办。比赛将持续5个小时参赛者在比赛期间需要吃一些甜点来补充能量。来自北京大学信息科学技术学院的小明为比赛准备了一些甜点。他想准备不同种类的甜点,包括月饼和包子等。每种甜点可以提供不同的能量,同时它们的大小也不一样。

小明使用箱子来包装这些甜点。不同的箱子可以容纳不同大小的甜点,不同的箱子的费用也不同。允许将一块甜点分割成若干部分把他们放入不同的箱子里带到比赛场地。注意如果被分割的甜点因为丢掉了其中的某些部分而无法复原,它将无法为参赛者提供能量。注意箱子没有必要装满。

小明想知道准备能量为P的甜点,他最少需要多少费用来购买箱子。

输入
输入包含若干测试样例。
输入的第一行是一个正整数T(T ≤ 10),代表测试样例数目。对于每组测试样例,第一行为3个正整数n,m,p ( 1 ≤ n ≤ 200,1 ≤ m ≤ 200,0 ≤ p ≤ 50000)分别代表甜点种类,箱子种类和参赛者比赛所需要补充的能量。
接下来的n行,每行包含3个整数ti, ui, vi ( 1 ≤ ti ≤ 100,1 ≤ ui ≤ 100,1 ≤ vi ≤ 100) , 代表第i类甜点可以提供ti的能量,它的大小为ui并且小明最多有vi个该种类的甜点。
接下来又有m行,每一行包含3个整数xi, yi, zi ( 1 ≤ xj ≤ 100,1 ≤ yj ≤ 100,1 ≤ zj ≤ 100), 代表第i类箱子可以容纳xi大小的甜点,该类箱子的单价yi,并且小明最多可以使用zi个该类的箱子。
输出
对于每组测试样例,请输出最小的箱子费用,并且费用不能超过50000。否则,输出FAIL。
样例输入
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答案需要使用long long表示
05表达式期望值,Ai小于2^20

全局题号
15289
提交次数
42
尝试人数
12
通过人数
9