Portals

Description:

Input:

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

Output:

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.

Sample Input:

4 3 7
7 4 17
3 0 8
11 2 0
13 3 5
3 1
2 1
4 3

Sample Output:

5

Sample Input:

4 3 7
7 4 17
3 0 8
11 2 0
13 3 5
3 1
2 1
4 1

Sample Output:

22

Sample Input:

4 3 7
7 4 17
3 0 8
11 2 0
14 3 5
3 1
2 1
4 3

Sample Output:

-1

Note:

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.