Description

你拥有 $T$ 分钟的时间。

做作业的顺序可以根据重要度 $v_i$ 来排序，但可能这不是最佳方案。且每项作业可能不止有一项，所以每项作业还有一个数量 $c_i$，每项 $t_i$ 分钟可以完成。

而在做某作业之前可能要先写完某个作业，所以还给出 $M$ 个关系，每个关系包含两个数 $a$，$b$ ，代表 $a$ 是 $b$ 完成的前提，不存在 $a=b$ 的情况。

关系不排除环的情况，cz 不想重做一遍作业，只好不做在环上的作业。

当某作业做到一半但时间结束，则失去该作业重要度；当该作业只做了 $k$ 个，但 $k\leq c_i$ ,则得到 $k\times v_i$ 重要度 , 如果该作业没把 $c_i$ 个做完，则不得做其他作业。

可存在 $b$ 有多个 $a$，但请注意一个作业的 一个 前提被做了以后，该作业就可以被做了。但cz非常专注，他写完一个作业以后就必须写以该作业为前提的作业。

Input Format

输入共 $N+M+2$ 行

第 $1$ 行输入 $2$ 个正整数 $N,T$。

接下来共 $N$ 行输入，第 $i$ 行输入 $3$ 个正整数 $v_i,c_i,t_i$。

第 $N+2$ 行输入 $1$ 个正整数 $1$ 行。

接下来共 $M$ 行输入，意义同上。

Output Format

输出共 $1$ 行 $1$ 个数，表示价值（重要度）最大值。

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

6

Hint

子任务

对于 $100\%$ 的数据，$1<=N<=10000,1<=M<=100000$

其他值均在$long long$范围内。

题目来源

MtOI2018 迷途の家の水题大赛 T1

出题人：Doubleen

56432