P5477 [MtOI2018] Grinding Problems? Homework Maniac!

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.

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**.

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 one line with one number, the maximum value (importance).

### Subtasks For $100\%$ of the testdata, $1