CF1271D Portals

你正在玩一款策略类电子游戏（是的，我们已经没有好题材了）。在这款游戏中，你指挥着一支庞大的军队，你的目标是征服对手的 $n$ 座城堡。 下面详细描述游戏过程。最开始你拥有 $k$ 名战士。你的敌人控制着 $n$ 座城堡；要征服第 $i$ 座城堡，你至少需要 $a_i$ 名战士（你在攻占城堡时不会损失任何战士，所以你的军队人数在战斗后保持不变）。每当你占领一座城堡后，你可以在该城堡招募新战士——具体来说，占领第 $i$ 座城堡后，会有 $b_i$ 名战士加入你的军队。此外，在占领一座城堡（或之后）你可以选择防守它：如果你在某座城堡中留下至少一名战士，该城堡就被视为已防守。每座城堡都有一个重要性参数 $c_i$，你的总得分为所有被防守城堡的重要性值之和。你有两种方式可以防守一座城堡： - 如果你当前在第 $i$ 座城堡，你可以留下一个战士来防守第 $i$ 座城堡； - 有 $m$ 个单向传送门连接着这些城堡。每个传送门由两个城堡编号 $u$ 和 $v$ 描述（对于每个传送门都有 $u > v$）。传送门的使用方式如下：如果你当前在第 $u$ 座城堡，你可以派遣一名战士通过传送门去防守第 $v$ 座城堡。 显然，当你命令一名战士去防守某座城堡时，他会离开你的军队。 你必须按照固定顺序依次攻占城堡：你必须先攻占第一座，然后是第二座，依此类推。在你攻占第 $i$ 座城堡后（但仅在攻占第 $i+1$ 座城堡之前），你可以在第 $i$ 座城堡招募新战士，留下战士防守第 $i$ 座城堡，并使用任意数量从第 $i$ 座城堡出发、指向编号更小城堡的传送门。只要你攻占了下一座城堡，这些针对第 $i$ 座城堡的操作就不再可用。 如果在游戏的某一时刻，你没有足够的战士去攻占下一座城堡，你就会失败。你的目标是最大化所有被防守城堡的重要性值之和（注意，在最后一座城堡中，你仍可以招募新战士、防守该城堡以及使用从该城堡出发的传送门——你的得分会在所有操作后统计）。 你能否制定出攻占和防守城堡的最优策略？

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 5000$，$0 \le m \le \min(\frac{n(n-1)}{2}, 3 \cdot 10^5)$，$0 \le k \le 5000$）——城堡数量、传送门数量和你初始的军队规模。 接下来 $n$ 行，每行描述一座城堡，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$0 \le a_i, b_i, c_i \le 5000$）——攻占第 $i$ 座城堡所需的战士数、在该城堡可招募的战士数以及该城堡的重要性值。 接下来 $m$ 行，每行描述一个传送门，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le v_i < u_i \le n$），表示有一条从第 $u_i$ 座城堡通往第 $v_i$ 座城堡的传送门。不会有重复的传送门。 保证在任何情况下你的军队规模都不会超过 $5000$（即 $k + \sum\limits_{i=1}^{n} b_i \le 5000$）。

如果无法攻占所有城堡，输出一个整数 $-1$。 否则，输出一个整数，表示所有被防守城堡的重要性值之和的最大值。

第一个样例的最佳操作如下： 1. 攻占第一座城堡； 2. 在第一座城堡招募新战士，此时你的军队有 $11$ 人； 3. 攻占第二座城堡； 4. 攻占第三座城堡； 5. 在第三座城堡招募新战士，此时你的军队有 $13$ 人； 6. 攻占第四座城堡； 7. 留下一个战士防守第四座城堡，此时你的军队有 $12$ 人。 这种操作方式（以及其他几种）都能获得 $5$ 的总得分。 第二个样例的最佳操作如下： 1. 攻占第一座城堡； 2. 在第一座城堡招募新战士，此时你的军队有 $11$ 人； 3. 攻占第二座城堡； 4. 攻占第三座城堡； 5. 在第三座城堡招募新战士，此时你的军队有 $13$ 人； 6. 攻占第四座城堡； 7. 留下一个战士防守第四座城堡，此时你的军队有 $12$ 人； 8. 通过第三条传送门派遣一名战士去防守第一座城堡，此时你的军队有 $11$ 人。 这种操作方式（以及其他几种）都能获得 $22$ 的总得分。 第三个样例中无法攻占最后一座城堡：你需要 $14$ 名战士，但在不攻占它的情况下最多只能积累 $13$ 名战士。 由 ChatGPT 4.1 翻译