你想要参加 ICPC（星际点数收集竞赛）。在这个竞赛中，我们需要在 $N$ 个网站（编号为 $1$ 到 $N$）之间移动，在给定的时间限制内尽可能多地收集点数。我们可以在任意网站开始和结束。

网站之间有 $M$ 条链接，我们可以通过这些链接在网站间移动。假设在网站间移动不需要时间。这些链接是有向的，且网站可能存在指向自身的链接。

在每个网站 $i$ 中，都有一个广告，观看该广告需要 $t_i$ 秒，观看后可以获得 $p_i$ 点数。当我们开始或进入一个网站时，可以决定是否观看广告。但是，在通过网站内的任何链接离开之前，我们不能观看同一个广告超过一次；而如果我们通过一条或多条链接（包括连接到自身的链接）在网站间移动并返回该网站后，则可以再次观看。此外，我们观看网站 $i$ 广告的次数不能超过 $k_i$ 次。

你希望通过尽可能多地收集点数来赢得比赛。因此，你需要计算在 $T$ 秒内能够收集到的最大点数。

输入格式

输入包含多组数据。数据集的数量不超过 $60$ 组。

每个数据集的第一行包含三个整数 $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$ 秒内能够收集到的最大点数。

样例

输入 1

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

输出 1

15
2014
0
25
40
390