你玩的是战略视频游戏(是的,我们已经没有好的问题图例了)。在这个游戏中,你控制着一支庞大的军队,你的目标是征服对手的$$$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$$$-th 行用三个整数描述第 $$$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$$$) 描述第 $$$i$$$ 入口,这意味着该入口从城堡 $$$u_i$$$ 通向城堡 $$$v_i$$$。没有列出两个相同的门户。
保证你的军队规模在任何情况下都不会超过$$$5000$$$(即$$$k + \sum\limits_{i = 1}^{n} b_i \le 5000$$$)。
输出
如果不可能占领所有城堡,则打印一个整数$$$-1$$$。
否则,打印一个等于被防御城堡的重要性值的最大总和的整数。
示例
输入 #1
4 3 7 7 4 17 3 0 8 11 2 0 13 3 5 3 1 2 1 4 3
输出 #1
5
输入 #2
4 3 7 7 4 17 3 0 8 11 2 0 13 3 5 3 1 2 1 4 1
输出 #2
22
输入 #3
4 3 7 7 4 17 3 0 8 11 2 0 14 3 5 3 1 2 1 4 3
输出 #3
-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$$$ 。