웹사이트 투어

ICPC(Internet Contest of Point Collection)에 나가려고 한다. 이 대회에서는 1번부터 N번까지 번호가 붙은 웹사이트 사이를 제한 시간 안에 돌아다니면서 점수를 최대한 많이 모은다. 출발하는 웹사이트와 마지막에 머무는 웹사이트는 마음대로 고를 수 있다.

웹사이트 사이에는 링크가 M개 있고, 이 링크를 타고 웹사이트를 옮겨 다닌다. 링크를 타고 이동하는 데 걸리는 시간은 0초로 본다. 링크에는 방향이 있고, 어떤 웹사이트에서 자기 자신으로 가는 링크도 있을 수 있다.

웹사이트 $i$에는 광고가 하나 있다. 이 광고를 $t_i$초 동안 보면 $p_i$점을 얻는다. 어떤 웹사이트에서 출발했거나 링크를 타고 그 웹사이트에 들어왔을 때, 광고를 볼지 말지 고를 수 있다. 다만 그 웹사이트에서 링크를 한 번도 쓰지 않은 채로 같은 광고를 두 번 볼 수는 없다. 링크를 하나 이상 타고 그 웹사이트로 다시 돌아왔다면 광고를 또 볼 수 있고, 자기 자신으로 가는 링크를 쓴 경우도 여기에 들어간다. 또 웹사이트 $i$의 광고는 전부 합쳐 $k_i$번을 넘게 볼 수 없다.

$T$초 안에 모을 수 있는 점수의 최댓값을 구하라.

입력은 여러 데이터셋으로 이루어진다. 데이터셋의 개수는 60개 이하다.

각 데이터셋의 형식은 다음과 같다.

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

각 데이터셋의 첫 줄에는 정수 세 개 $N$ ($1 \le N \le 100$), $M$ ($0 \le M \le 1000$), $T$ ($1 \le T \le 10000$)이 주어진다. 차례대로 웹사이트의 수, 링크의 수, 제한 시간이다. 입력에 나오는 시간의 단위는 모두 초다.

다음 $N$개 줄에는 광고 정보가 주어진다. 그중 $i$번째 줄에는 정수 세 개 $p_i$ ($1 \le p_i \le 10000$), $t_i$ ($1 \le t_i \le 10000$), $k_i$ ($1 \le k_i \le 10000$)가 주어진다. 차례대로 웹사이트 $i$의 광고 점수, 그 광고를 보는 데 걸리는 시간, 그 광고를 볼 수 있는 최대 횟수다.

다음 $M$개 줄에는 링크 정보가 주어진다. 각 줄에는 정수 두 개 $a_i$와 $b_i$ ($1 \le a_i, b_i \le N$)가 주어지고, 웹사이트 $a_i$에서 웹사이트 $b_i$로 가는 링크가 있다는 뜻이다.

입력의 끝은 0이 세 개 적힌 줄로 표시한다.

각 데이터셋마다 $T$초 안에 모을 수 있는 점수의 최댓값을 한 줄에 하나씩 출력한다.