为了获得购买新风能爆能枪的资金,游侠 Qwerty 决定从事一段时间的贸易。他想在其中一个星球上购买一定数量的物品(或者可能根本不买任何东西),然后在另一个星球上出售购买的物品。注意,此操作不重复,即买入和卖出仅进行一次。为了执行他的计划,Qwerty 将申请一笔银行贷款来支付所有费用,并在手术结束时归还借来的钱(这笔钱不计利息地归还)。同时,Querty 希望获得尽可能多的利润。
该系统共有n颗行星。在每个 Qwerty 上,Qwerty 都可以购买或出售 m 种类型的物品(例如食物、药品、武器、酒精等)。对于每个行星 i 和每种类型的项目 j,Qwerty 知道以下内容:
- aij — 购买物品的成本;
- bij — 销售物品的成本;
- cij — 剩余项目数。
不允许在行星 i 上购买超过 cij 类型 j 的物品,但允许出售任意数量的任何种类的物品。
已知 Qwerty 的船舱最多可容纳 k 件物品,请确定 Qwerty 可以获得的最大利润。
输入
第一行包含三个空格分隔的整数 n、m 和 k (2 ≤ n ≤ 10, 1 ≤ m, k ≤ 100) — 相应地,行星数量、问题类型数量和 Qwerty 船舱容量。
然后遵循描述每个行星的 n 个块。
第 i 个块的第一行将行星的名称作为长度为 1 到 10 个拉丁字母的字符串。名字的第一个字母大写,其余字母小写。然后在第 i 个块中的 m 行中,其中第 j 行包含三个整数 aij、bij 和 cij (1 ≤ bij < aij ≤ 1000, 0 ≤ cij ≤ 100) — 这些数字描述了第 i 个星球上第 j 个项目的货币操作。行中的数字由空格分隔。
保证所有行星的名称都是不同的。
输出
打印一个数字——Qwerty 可以获得的最大利润。
示例
输入 #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
注意
在第一个测试用例中,您应该飞往金星,贷款 74 单位货币并购买 3 件第一类物品和 7 件第三类物品 (3·6 + 7·8 = 74)。然后护林员应该飞往地球并在那里出售他购买的所有物品。他获得 3·9 + 7·9 = 90 个单位的物品钱,他应该借出其中的 74 个单位。由此产生的利润等于 16 个货币单位。在这种情况下我们无法获得更多的利润。