Background

After hearing that summer vacation is coming to an end, the magical cz finally realized that he cannot finish his homework.

Before he finishes the homework, you need to tell him the order in which to do it, so that you can play together.

Problem Description

You have $T$ minutes.

The order of doing homework can be sorted by importance $v_i$, but this may not be the best strategy. Also, each type of homework may have more than one item, so each homework also has a quantity $c_i$, and each item takes $t_i$ minutes to complete.

Before doing some homework, it may be necessary to finish some other homework first, so $M$ relations are given. Each relation contains two numbers $a$, $b$, meaning that $a$ is a prerequisite for completing $b$. There is no case where $a=b$.

The relations may contain cycles. cz does not want to redo homework, so he can only skip the homework that lies on cycles.

If the time ends when a homework is only half done, then you gain no importance from that homework. If for a homework you finish only $k$ items, and $k\leq c_i$, then you gain $k\times v_i$ importance. If you do not finish all $c_i$ items of that homework, then you are not allowed to do any other homework.

A homework $b$ may have multiple prerequisites $a$. However, note that once one prerequisite of a homework is done, that homework can be done. But cz is very focused: after finishing one homework, he must do the homework that uses this homework as a prerequisite.

Input Format

The input has $N+M+2$ lines.

Line $1$ contains two positive integers $N,T$.

The next $N$ lines follow. Line $i$ contains three positive integers $v_i,c_i,t_i$.

Line $N+2$ contains one positive integer $1$.

The next $M$ lines describe the relations, with the same meaning as above.

Output Format

Output one line with one number, the maximum value (importance).

4 7
2 1 1
2 1 2
2 1 3
2 1 4
3
3 4
2 3
1 2

6

Hint

Subtasks

For $100\%$ of the testdata, $1<=N<=10000,1<=M<=100000$.

All other values are within the range of $long long$.

Source

MtOI2018 迷途の家の水题大赛 T1

Problem setter: Doubleen

56432

Translated by ChatGPT 5