Website Tour

Problem Statement

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.

Input

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.

Output

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

Sample Input

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

Output for the Sample Input

15 2014 0 25 40 390

Example

Input

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

Output

15 2014 0 25 40 390

inputFormat

Input

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.

outputFormat

Output

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

Sample Input

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

Output for the Sample Input

15 2014 0 25 40 390

Example

Input

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

Output

15 2014 0 25 40 390

样例

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

</p>