← 返回题目列表

AtCoder · icpc2014autumn_j

J. 网站游览

中文机器翻译题面 查看原题

问题陈述

您想参加 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