问题陈述
您想参加 ICPC(互联网积分收集大赛)。 在本次比赛中,我们在规定的时间内在$N$个网站(编号为$1$到$N$)中移动并收集尽可能多的积分。 我们可以在任何网站上开始和结束。
网站之间有 $M$ 链接,我们可以使用这些链接在网站之间移动。 您可以假设在网站之间移动不需要时间。 这些链接是定向的,网站可能有指向其自身的链接。
每个网站$i$都有一个广告,我们可以在$t_i$秒内观看该广告获得$p_i$积分。 当我们开始或进入一个网站时,我们可以决定是否观看广告。 但是,在使用网站中的任何链接之前,我们不能多次观看同一广告,而如果我们在网站之间移动并使用一个或多个链接(包括将网站与其自身连接的链接)返回到该网站,我们可以再次观看该广告。 此外,我们在网站 $i$ 上观看广告的次数不能超过 $k_i$ 次。
您想通过收集尽可能多的积分来赢得这场比赛。 因此,您决定计算在 $T$ 秒内可以收集的最大分数。
输入
输入由多个数据集组成。 数据集数量不超过60美元。
每个数据集的格式如下。
$N$ $M$ $T$
$p_1$ $t_1$ $k_1$
:
:
$p_N$ $t_N$ $k_N$
$a_1$ $b_1$
:
:
$a_M$ $b_M$
每个数据集的第一行包含三个整数$N$ ($1 \le N \le 100$)、$M$ ($0 \le M \le 1{,}000$) 和 $T$ ($1 \le T \le 10{,}000$),分别表示网站数量、链接数量和时间限制。 输入中给出的所有时间均以秒为单位表示。
下面的$N$行描述了广告的信息。 其中第$i$包含三个整数$p_i$ ($1 \le p_i \le 10{,}000$)、$t_i$ ($1 \le t_i \le 10{,}000$)和$k_i$ ($1 \le k_i \le 10{,}000$),分别表示广告的点数、观看广告所需的时间和最大次数您可以分别在$i$网站上观看广告。
下面的 $M$ 行描述了链接的信息。 每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i,b_i \le N$),这意味着我们可以使用链接从网站 $a_i$ 移动到网站 $b_i$。
输入的结束由包含三个零的行表示。
输出
对于每个数据集,输出您在 $T$ 秒内可以收集的最大分数。
示例输入
5 4 10 4 3 1 6 4 3 3 2 4 2 2 1 8 5 3 1 2 2 3 3 4 4 5 3 3 1000 1000 1 100 1 7 100 10 9 100 1 2 2 3 3 2 1 0 5 25 25 2 1 0 25 25 25 2 5 5 100 1 1 20 1 1 20 10 1 1 10 1 1 10 1 1 1 2 2 1 3 4 4 5 5 3 3 3 100 70 20 10 50 15 20 90 10 10 1 2 2 2 2 3 0 0 0
样本输入的输出
15 2014 0 25 40 390