You want to compete in ICPC (Internet Contest of Point Collection). In this contest, we move around in $N$ websites, numbered $1$ through $N$, within a time limit and collect points as many as possible. We can start and end on any website.

There are $M$ links between the websites, and we can move between websites using these links. You can assume that it doesn't take time to move between websites. These links are directed and websites may have links to themselves.

In each website $i$, there is an advertisement and we can get $p_i$ point(s) by watching this advertisement in $t_i$ seconds. When we start on or move into a website, we can decide whether to watch the advertisement or not. But we cannot watch the same advertisement more than once before using any link in the website, while we can watch it again if we have moved among websites and returned to the website using one or more links, including ones connecting a website to itself. Also we cannot watch the advertisement in website $i$ more than $k_i$ times.

You want to win this contest by collecting as many points as you can. So you decided to compute the maximum points that you can collect within $T$ seconds.

The input consists of multiple datasets. The number of dataset is no more than $60$.

Each dataset is formatted as follows.

$N$ $M$ $T$

$p_1$ $t_1$ $k_1$

:

:

$p_N$ $t_N$ $k_N$

$a_1$ $b_1$

:

:

$a_M$ $b_M$

The first line of each dataset contains three integers $N$ ($1 \le N \le 100$), $M$ ($0 \le M \le 1{,}000$) and $T$ ($1 \le T \le 10{,}000$), which denote the number of websites, the number of links, and the time limit, respectively. All the time given in the input is expressed in seconds.

The following $N$ lines describe the information of advertisements. The $i$-th of them contains three integers $p_i$ ($1 \le p_i \le 10{,}000$), $t_i$ ($1 \le t_i \le 10{,}000$) and $k_i$ ($1 \le k_i \le 10{,}000$), which denote the points of the advertisement, the time required to watch the advertisement, and the maximum number of times you can watch the advertisement in website $i$, respectively.

The following $M$ lines describe the information of links. Each line contains two integers $a_i$ and $b_i$ ($1 \le a_i,b_i \le N$), which mean that we can move from website $a_i$ to website $b_i$ using a link.

The end of input is indicated by a line containing three zeros.

For each dataset, output the maximum points that you can collect within $T$ seconds.

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

Source: JAG Practice Contest for ACM-ICPC Asia Regional 2014
, Japan, 2014-09-14

http://acm-icpc.aitea.net/

http://jag2014autumn.contest.atcoder.jp/

http://acm-icpc.aitea.net/

http://jag2014autumn.contest.atcoder.jp/