问题陈述

你想参加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```

### 样例输出

```plain
15
2014
0
25
40
390```

---

### 题目来源

JAG Practice Contest for ACM-ICPC Asia Regional 2014