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