CF176A.Trading Business

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.

为了购买一把新型的永恒冲击枪（aeonic blaster），游侠 Qwerty 决定暂时从事贸易活动。他计划在某一颗行星上购买若干件物品（也可能一件都不买），然后将所购物品全部运送到另一颗行星上出售。注意，该操作仅执行一次，即仅进行一次购买和一次出售。为实施该计划，Qwerty 将向银行申请一笔贷款，用以覆盖全部开支，并在交易结束后全额归还贷款本金（不计利息）。与此同时，Qwerty 希望获得尽可能高的利润。

整个星系共有 $ n $ 颗行星。在每颗行星上，Qwerty 均可买卖 $ m $ 种类型的物品（例如食物、药品、武器、酒精等）。对于每颗行星 $ i $ 和每种物品类型 $ j $，Qwerty 已知以下信息：

• $ a_{ij} $ —— 在行星 $ i $ 上购买一件类型 $ j $ 物品的成本；
• $ b_{ij} $ —— 在行星 $ i $ 上出售一件类型 $ j $ 物品的售价；
• $ c_{ij} $ —— 行星 $ i $ 上类型 $ j $ 物品的剩余数量。

在行星 $ i $ 上，类型 $ j $ 的物品最多只能购买 $ c_{ij} $ 件；但出售时则无数量限制（即可以出售任意数量的任意种类物品）。

已知 Qwerty 的飞船货舱容量至多为 $ k $ 件物品，请计算 Qwerty 能获得的最大利润。

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.

第一行包含三个以空格分隔的整数 $n$、$m$ 和 $k$（$2 \leq n \leq 10$，$1 \leq m, k \leq 100$），分别表示星球的数量、问题类型的数量以及 Qwerty 飞船货舱的容量。

随后是 $n$ 个块，每个块描述一个星球。

第 $i$ 个块的第一行是一个长度为 $1$ 至 $10$ 的字符串，表示该星球的名称；名称由拉丁字母组成，首字母大写，其余字母小写。接着，在第 $i$ 个块中还有 $m$ 行，其中第 $j$ 行包含三个整数 $a_{ij}$、$b_{ij}$ 和 $c_{ij}$（$1 \leq b_{ij} < a_{ij} \leq 1000$，$0 \leq c_{ij} \leq 100$），用于描述在第 $i$ 个星球上对第 $j$ 种物品进行的金钱操作。每行中的数字以空格分隔。

保证所有星球的名称互不相同。

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

输出一个整数——Qwerty 能获得的最大利润。

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.

在第一个测试用例中，你应该飞往金星，在那里借入 74 单位货币，并购买 3 件第一类物品和 7 件第三类物品（$3\cdot6 + 7\cdot8 = 74$）。然后，游骑兵应飞往地球，并在那里出售所有已购入的物品。他将获得 $3\cdot9 + 7\cdot9 = 90$ 单位货币；其中需偿还贷款 74 单位。最终利润为 16 单位货币。在此情况下，我们无法获得更高的利润。