达达斯经营着 座棱晶矿山,并准备制造 个采矿模块。
第 个模块有 种候选设计,必须恰好选择其中一种。采用第 种设计时,该模块的性能为 ,每小时消耗 个棱晶。所有模块都必须制造。无论有多少座矿山使用该模块,其消耗量都只计算一次;没有矿山使用的模块也要计算消耗量。
第 座矿山使用两个不同的模块 。设第 个模块选择的设计编号为 ,则该矿山每小时开采 个棱晶。多个矿山可以同时使用同一个模块。多座矿山也可以使用同一对模块,此时每座矿山的产量都分别计入总产量。
每小时净收益等于所有矿山的总产量减去所有模块的总消耗量。求每小时净收益的最大值。
输入格式如下:
输出每小时净收益的最大值。答案可能为负数。
第一行给出矿山数量 和模块数量 。接下来的 行给出每个模块的候选设计数量,以及每种设计的性能和消耗量。最后 行给出每座矿山使用的两个模块的编号。候选设计不保证按性能排序。
| 3 | 55 | 没有额外限制。 |