Trading Business

题意翻译

### 题面 在一个星系中，有$n$ 个星球。每个星球上都有$m$ 种物品可供购买或销售，并知道以下信息： 1. 在第$i$ 个星球上购买第$j$ 个物品需要的花费是$a_{i,j}$ 。 2. 在第$i$ 个星球上销售第$j$ 个物品得到的回报是$b_{i,j}$ 。 3. 在第$i$ 个星球上第$j$ 个物品的库存是$c_{i,j}$ 。你不能够购买超过库存数量的物品数，但是可以在任意星球销售任意数量的物品。 4. 在每一个星球你购买的物品总数不能超过$k$ 。 你只能在任意两个星球间进行一次购买并卖出，求最大收益。 ### 输入输出格式 ##### 输入 * 第一行包括$n,m,k(2\le n\le 10,1\le m,k\le 100)$ ，含义如上。 * 接下来有$n$ 组数据，每组数据描述一个星球： 1. 第一行一个字符串$S(1\le|S|\le10)$ ，表示这个星球的名称。 2. 接下来$m$ 行，每行三个数$a_{i,j},b_{i,j},c_{i,j}(a_{i,j},b_{i,j}\le 1000,c_{i,j}\le 100)$ ，描述在第$i$ 个星球上第$j$ 个物品的信息。 ##### 输出 输出仅一个整数，表示最大收益。 Translated by @frankchenfu

题目描述

To get money for a new aeonic blaster, ranger Qwerty decided to engage in trade for a while. He wants to buy some number of items (or probably not to buy anything at all) on one of the planets, and then sell the bought items on another planet. Note that this operation is not repeated, that is, the buying and the selling are made only once. To carry out his plan, Qwerty is going to take a bank loan that covers all expenses and to return the loaned money at the end of the operation (the money is returned without the interest). At the same time, Querty wants to get as much profit as possible. The system has $ n $ planets in total. On each of them Qwerty can buy or sell items of $ m $ types (such as food, medicine, weapons, alcohol, and so on). For each planet $ i $ and each type of items $ j $ Qwerty knows the following: - $ a_{ij} $ — the cost of buying an item; - $ b_{ij} $ — the cost of selling an item; - $ c_{ij} $ — the number of remaining items. It is not allowed to buy more than $ c_{ij} $ items of type $ j $ on planet $ i $ , but it is allowed to sell any number of items of any kind. Knowing that the hold of Qwerty's ship has room for no more than $ k $ items, determine the maximum profit which Qwerty can get.

输入输出格式

输入格式

The first line contains three space-separated integers $ n $ , $ m $ and $ k $ ( $ 2<=n<=10 $ , $ 1<=m,k<=100 $ ) — the number of planets, the number of question types and the capacity of Qwerty's ship hold, correspondingly. Then follow $ n $ blocks describing each planet. The first line of the $ i $ -th block has the planet's name as a string with length from $ 1 $ to $ 10 $ Latin letters. The first letter of the name is uppercase, the rest are lowercase. Then in the $ i $ -th block follow $ m $ lines, the $ j $ -th of them contains three integers $ a_{ij} $ , $ b_{ij} $ and $ c_{ij} $ ( $ 1<=b_{ij}<a_{ij}<=1000 $ , $ 0<=c_{ij}<=100 $ ) — the numbers that describe money operations with the $ j $ -th item on the $ i $ -th planet. The numbers in the lines are separated by spaces. It is guaranteed that the names of all planets are different.

输出格式

Print a single number — the maximum profit Qwerty can get.

输入输出样例

输入样例 #1

3 3 10
Venus
6 5 3
7 6 5
8 6 10
Earth
10 9 0
8 6 4
10 9 3
Mars
4 3 0
8 4 12
7 2 5

输出样例 #1

16

说明

In the first test case you should fly to planet Venus, take a loan on 74 units of money and buy three items of the first type and 7 items of the third type ( $ 3·6+7·8=74 $ ). Then the ranger should fly to planet Earth and sell there all the items he has bought. He gets $ 3·9+7·9=90 $ units of money for the items, he should give 74 of them for the loan. The resulting profit equals 16 units of money. We cannot get more profit in this case.