This page is still under construction.

Parts of this page are still being built. What you see may change.

Website Tour

Time limit8sMemory limit512 MB

Summary
Walk a directed graph of N websites, watching ads (points p, time t, at most k times each) to maximize points within T seconds.
Level

Hard8 of 10

Topics
Graph, Dynamic programming, Greedy, Union-find
Solved
No attempts yet

Problem

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 ii carries one advertisement. Watching it for tit_i seconds earns pip_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 ii may be watched at most kik_i times in total.

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

Input

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 NN (1≤N≤1001 \le N \le 100), MM (0≤M≤10000 \le M \le 1000) and TT (1≤T≤100001 \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 NN lines describe the advertisements. The ii-th of them holds three integers pip_i (1≤pi≤100001 \le p_i \le 10000), tit_i (1≤ti≤100001 \le t_i \le 10000) and kik_i (1≤ki≤100001 \le k_i \le 10000): the points of the advertisement on website ii, the time needed to watch it, and the largest number of times you may watch it.

The next MM lines describe the links. Each line holds two integers aia_i and bib_i (1≤ai,bi≤N1 \le a_i, b_i \le N), meaning there is a link from website aia_i to website bib_i.

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

Output

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

Examples5

  1. Example 1

    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
    Expected output
    15
2014
0
25
40
390

  2. Example 2

    Input
    1 0 1
1 1 1
0 0 0
    Expected output
    1

  3. Example 3

    Input
    1 1 10000
1 1 10000
1 1
1 1 10000
7 3 5
1 1
0 0 0
    Expected output
    10000
35

  4. Example 4

    Input
    1 0 10000
10000 1 10000
0 0 0
    Expected output
    10000

  5. Example 5

    Input
    4 3 10
1 10 5
100 5 5
1 10 5
100 5 5
1 2
2 3
3 4
0 0 0
    Expected output
    200