Website Tour

You are entering ICPC (Internet Contest of Point Collection). In this contest you move around N websites, numbered 1 through N, within a time limit and collect as many points as you can. You may start at any website and finish at any website.

There are M links between the websites, and you move from one website to another along them. Moving along a link takes 0 seconds. Links are directed, and a link may lead from a website back to itself.

Website $i$ carries one advertisement. Watching it for $t_i$ seconds earns $p_i$ points. When you start at a website, or arrive at one through a link, you choose whether to watch its advertisement. You may not watch the same advertisement twice without using a link at that website. Once you have used one or more links and come back, you may watch it again, and a link that leads from a website to itself counts for this. The advertisement on website $i$ may be watched at most $k_i$ times in total.

Find the largest number of points you can collect within $T$ seconds.

The input holds several datasets. There are at most 60 datasets.

Each dataset has the following format.

N M T
p1 t1 k1
:
:
pN tN kN
a1 b1
:
:
aM bM

The first line of a dataset holds three integers $N$ ($1 \le N \le 100$), $M$ ($0 \le M \le 1000$) and $T$ ($1 \le T \le 10000$): the number of websites, the number of links, and the time limit. Every time value in the input is given in seconds.

The next $N$ lines describe the advertisements. The $i$-th of them holds three integers $p_i$ ($1 \le p_i \le 10000$), $t_i$ ($1 \le t_i \le 10000$) and $k_i$ ($1 \le k_i \le 10000$): the points of the advertisement on website $i$, the time needed to watch it, and the largest number of times you may watch it.

The next $M$ lines describe the links. Each line holds two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), meaning there is a link from website $a_i$ to website $b_i$.

A line holding three zeros marks the end of the input.

For each dataset, print on its own line the largest number of points you can collect within $T$ seconds.