CF176A Trading Business

为了购买一把新的 aeonic blaster，巡逻队员 Qwerty 决定暂时从事贸易。他打算在某个星球上购买一定数量的物品（也可以什么都不买），然后把买到的物品在另一个星球上卖出。需要注意的是，这个操作只进行一次，即买和卖各仅进行一次。为了实施他的计划，Qwerty 打算向银行贷款以支付所有开销，并在操作结束时归还贷款（不计利息）。同时，Qwerty 希望获得尽可能多的利润。 系统中总共有 $n$ 个星球。在每一个星球上，Qwerty 都可以购买或售卖 $m$ 类物品（如粮食、药品、武器、酒精等）。对于每个星球 $i$ 和每种物品 $j$，Qwerty 知道以下信息： - $a_{ij}$ —— 购买一件该物品的价格； - $b_{ij}$ —— 售出一件该物品的价格； - $c_{ij}$ —— 剩余可购买的该物品数量。 在星球 $i$ 上购买第 $j$ 类物品时，最多只能买 $c_{ij}$ 件，但出售任何种类的物品时不限数量。 已知 Qwerty 的飞船货舱最多只能容纳 $k$ 件物品，求 Qwerty 能获得的最大利润。

第一行包含三个用空格分隔的整数 $n$、$m$ 和 $k$（$2 \leq n \leq 10$，$1 \leq m,k \leq 100$）——星球数量、物品类型数以及 Qwerty 飞船货舱的容量。 接下来是 $n$ 个描述每个星球的区块。 第 $i$ 个区块第一行是该星球的名称，一个长度为 $1$ 到 $10$ 的仅由拉丁字母组成的字符串，首字母大写，其余为小写。接着，该区块有 $m$ 行，第 $j$ 行包含三个整数 $a_{ij}$、$b_{ij}$、$c_{ij}$（$1 \leq b_{ij} < a_{ij} \leq 1000$，$0 \leq c_{ij} \leq 100$），这三个数描述了第 $j$ 种物品在该星球上的买卖情况。每行的数以空格分隔。 保证所有星球的名称均不相同。

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

在第一个样例中，可以飞往星球 Venus，在那里贷款 74 单位的钱，购买三件第一种物品和七件第三种物品（$3 \times 6 + 7 \times 8 = 74$）。然后飞往 Earth，将所有购入的物品售出，可以得到 $3 \times 9 + 7 \times 9 = 90$ 单位的钱，还掉贷款 74 单位，最终利润为 16 单位。此方案下无法获得更多利润。 由 ChatGPT 5 翻译