Portals

题意翻译

你在玩一款游戏。 在这个游戏里面，你掌控着一只大军，你的目标是占领全部的 $n$ 个敌方的城堡。 让我们详细的介绍一下这个游戏。 最开始，你掌控着一只有 $k$ 个人的军队，你的敌人有 $n$ 个城堡。 为了占领第 $i$ 个城堡，你需要至少 $a_i$ 个士兵（你游戏玩的很好，所以你并不会损失士兵）。 当你占领了第 $i$ 个城堡后，你可以扩军。其中在第 $i$ 个城堡，你可以得到 $b_i$ 个士兵。 此外，在你占领了一个城堡后，你可以派至少一个兵驻守。每个城堡有一个重要值 $c_i$ ，你的总分就是所有你派兵驻守了的城堡的 $c_i$ 的和。 有两种方式派兵： - 你刚占领这个城堡，可以立马派兵驻守。 - 有 $m$ 条小路，其中第 $i$ 条是从 $u$ 通往 $v$ 。保证 $u>v$ 。你可以使用这条小路当且仅当你当前在 $u$ ，且拥有至少一个士兵可以派往 $v$ 。 显然，如果一个士兵被派去驻守，他就离开了你的军队。 你需要按照从 $1$ 到 $n$ 的顺序依次攻打。 假设你当前在 $i$ ，当你攻占 $i+1$ 时，所有在 $i$ 处的小路就不能用了。 如果在游戏中你没有足够的士兵去攻打下一座城堡，你就输了。 你的目标是在胜利的前提下最大化得分。 ### 数据范围 $1\leq n\leq 5000,0\leq m\leq \min(\frac{n(n-1)}{2},3\cdot 10^5),0\leq k\leq 5000$ 同时满足 $k+\sum b_i\leq 5000$ 。

题目描述

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 > 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?

输入输出格式

输入格式

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 < 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 $ ).

输出格式

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

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

说明

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.