← 返回题目列表

Codeforces · 176/A

A. 贸易业务

中文机器翻译题面 查看原题

为了获得购买新风能爆能枪的资金,游侠 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 个货币单位。在这种情况下我们无法获得更多的利润。