CF1271D.Portals

You play a strategic video game (yeah, we ran out of good problem legends). In this game you control a large army, and your goal is to conquer $n$ castles of your opponent.

Let's describe the game process in detail. Initially you control an army of $k$ warriors. Your enemy controls $n$ castles; to conquer the $i$-th castle, you need at least $a_i$ warriors (you are so good at this game that you don't lose any warriors while taking over a castle, so your army stays the same after the fight). After you take control over a castle, you recruit new warriors into your army — formally, after you capture the $i$-th castle, $b_i$ warriors join your army. Furthermore, after capturing a castle (or later) you can defend it: if you leave at least one warrior in a castle, this castle is considered defended. Each castle has an importance parameter $c_i$, and your total score is the sum of importance values over all defended castles. There are two ways to defend a castle:

• if you are currently in the castle $i$, you may leave one warrior to defend castle $i$;
• there are $m$ one-way portals connecting the castles. Each portal is characterised by two numbers of castles $u$ and $v$ (for each portal holds $u \gt v$). A portal can be used as follows: if you are currently in the castle $u$, you may send one warrior to defend castle $v$.

Obviously, when you order your warrior to defend some castle, he leaves your army.

You capture the castles in fixed order: you have to capture the first one, then the second one, and so on. After you capture the castle $i$ (but only before capturing castle $i + 1$) you may recruit new warriors from castle $i$, leave a warrior to defend castle $i$, and use any number of portals leading from castle $i$ to other castles having smaller numbers. As soon as you capture the next castle, these actions for castle $i$ won't be available to you.

If, during some moment in the game, you don't have enough warriors to capture the next castle, you lose. Your goal is to maximize the sum of importance values over all defended castles (note that you may hire new warriors in the last castle, defend it and use portals leading from it even after you capture it — your score will be calculated afterwards).

Can you determine an optimal strategy of capturing and defending the castles?

你正在玩一款策略类电子游戏（是的，我们已经用光了所有精彩的故事背景）。在这款游戏中，你指挥一支庞大的军队，目标是攻占对手的 $n$ 座城堡。

下面详细描述游戏流程。初始时，你拥有 $k$ 名战士。你的敌人控制着 $n$ 座城堡；要攻占第 $i$ 座城堡，你至少需要 $a_i$ 名战士（你在此游戏中实力超群，攻占城堡时不会损失任何战士，因此你的军队人数在战斗后保持不变）。每当你占领一座城堡，便会招募新战士加入你的军队——形式化地说，攻占第 $i$ 座城堡后，会有 $b_i$ 名战士加入你的军队。此外，在占领某座城堡（或之后）时，你可以选择防守该城堡：若你在某座城堡中至少留下一名战士，则该城堡即被视为已防守。每座城堡有一个重要性参数 $c_i$，而你的总得分等于所有已被防守的城堡的重要性值之和。防守一座城堡有两种方式：

• 若你当前位于第 $i$ 座城堡，你可以留下一名战士来防守该城堡；
• 存在 $m$ 个单向传送门连接各城堡。每个传送门由两个城堡编号 $u$ 和 $v$ 描述（对每个传送门均有 $u > v$）。传送门的使用方式如下：若你当前位于第 $u$ 座城堡，则可派遣一名战士去防守第 $v$ 座城堡。

显然，当你命令一名战士去防守某座城堡时，该战士将离开你的军队。

你必须按固定顺序攻占城堡：先攻占第一座，再攻占第二座，依此类推。在攻占第 $i$ 座城堡之后（但尚未攻占第 $i+1$ 座城堡之前），你可以执行以下操作：从第 $i$ 座城堡招募新战士、留下一名战士防守第 $i$ 座城堡，并任意多次使用从第 $i$ 座城堡出发、通往编号更小的其他城堡的传送门。一旦你开始攻占下一座城堡，针对第 $i$ 座城堡的这些操作将不再可用。

若在游戏过程中某一时刻，你拥有的战士数量不足以攻占下一座城堡，则你失败。你的目标是最大化所有已被防守的城堡的重要性值之和（注意：你可以在攻占最后一座城堡后继续招募新战士、防守该城堡，并使用从此城堡出发的所有传送门——你的最终得分将在所有操作完成后计算）。

你能确定一套攻占与防守城堡的最优策略吗？

The first line contains three integers $n$, $m$ and $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$) — the number of castles, the number of portals and initial size of your army, respectively.

Then $n$ lines follow. The $i$-th line describes the $i$-th castle with three integers $a_i$, $b_i$ and $c_i$ ($0 \le a_i, b_i, c_i \le 5000$) — the number of warriors required to capture the $i$-th castle, the number of warriors available for hire in this castle and its importance value.

Then $m$ lines follow. The $i$-th line describes the $i$-th portal with two integers $u_i$ and $v_i$ ($1 \le v_i \lt u_i \le n$), meaning that the portal leads from the castle $u_i$ to the castle $v_i$. There are no two same portals listed.

It is guaranteed that the size of your army won't exceed $5000$ under any circumstances (i. e. $k + \sum\limits_{i = 1}^{n} b_i \le 5000$).

第一行包含三个整数 $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$ 座城堡：$a_i$ 表示攻占该城堡所需的战士数量，$b_i$ 表示可在该城堡招募的战士数量，$c_i$ 表示该城堡的重要性值。

接下来是 $m$ 行。第 $i$ 行用两个整数 $u_i$ 和 $v_i$（$1 \le v_i \lt u_i \le n$）描述第 $i$ 个传送门，表示该传送门从城堡 $u_i$ 通向城堡 $v_i$。不会出现重复的传送门。

保证在任何情况下你的军队规模均不会超过 $5000$（即 $k + \sum\limits_{i = 1}^{n} b_i \le 5000$）。

If it's impossible to capture all the castles, print one integer $-1$.

Otherwise, print one integer equal to the maximum sum of importance values of defended castles.

如果无法攻占所有城堡，则输出一个整数 $-1$。

否则，输出一个整数，表示被成功防守的城堡的重要性值之和的最大值。

The best course of action in the first example is as follows:

1. capture the first castle;
2. hire warriors from the first castle, your army has $11$ warriors now;
3. capture the second castle;
4. capture the third castle;
5. hire warriors from the third castle, your army has $13$ warriors now;
6. capture the fourth castle;
7. leave one warrior to protect the fourth castle, your army has $12$ warriors now.

This course of action (and several other ones) gives $5$ as your total score.

The best course of action in the second example is as follows:

1. capture the first castle;
2. hire warriors from the first castle, your army has $11$ warriors now;
3. capture the second castle;
4. capture the third castle;
5. hire warriors from the third castle, your army has $13$ warriors now;
6. capture the fourth castle;
7. leave one warrior to protect the fourth castle, your army has $12$ warriors now;
8. send one warrior to protect the first castle through the third portal, your army has $11$ warriors now.

This course of action (and several other ones) gives $22$ as your total score.

In the third example it's impossible to capture the last castle: you need $14$ warriors to do so, but you can accumulate no more than $13$ without capturing it.

第一个样例中的最优行动方案如下：

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$ 名战士。