Problem 2184. -- 想赚钱的Tim

2184: 想赚钱的Tim

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 66  Accepted: 4
[Submit][Status][Web Board]

Description

Tim最近想自己赚钱出去旅游,他想到的最好的方法就是在几个超市之间倒卖东西。一共有n个超市,每个超市都有m件物品。Tim知道在每件物品在每个超市买入和卖出的价格,也知道在每个超市每样物品的个数。为了不被超市的人发现自己在倒卖东西,Tim最多只能倒卖K件商品。现在Tim请你帮他计算出他能获得的最大利润。

Input

多组测试,第一行输入超市数n,商品数m和可以倒卖的件数k(1<n<11,0<m,k<101)。接下来输入n个超市的情况,每个超市的情况占m+1行,首先输入超市的名字(超市的名字不超过10个字符),接下来m行分别输入ai,bi,ci(0<bi<ai<1001,ci<101)——分别代表i类物品在该超市买入的价格,i类物品在该超市卖出的价格以及i类物品在该超市的数量。输入保证超市名称不相同。

Output

输出Tim最多能赚多少钱。

Sample Input

2 1 5
A
6 5 5
B
10 9 0
2 2 5
Abcdefghij
20 15 20
10 5 13
Klmopqrstu
19 16 20
12 7 14

Sample Output

15
0

Author

胡辰

[Submit][Status][Web Board]