瑶瑶饿了

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

你们肯定都不知道从前有个很聪明的妹子,她的名字叫瑶瑶(tsyao)。一天,瑶瑶在自己家里建造了一个魔法阵。她在魔法阵找吃的,这个魔法阵有n种食物,每种食物有xi份,而且每种食物位于魔法阵的不同位置(相同食物位于相同位置)。吃第i种食物,每一份会消耗ti的时间,获得wi的价值。当然这个魔法阵有魔力,每次吃一种食物后瑶瑶会传送回到自己家(耗时0),并且不能再吃该种食物。

另外,从魔法阵x位置到y位置会消耗bi的时间。如果有路能够让瑶瑶从x到达z,从z到达y,那么瑶瑶是可以从x经过z到达y的,但是瑶瑶不能在z点吃东西,否则她又会被送回家。。。。

现在瑶瑶家位于0号位置,她有T的时间吃食物,她想在T时间内吃得最大的价值。

Input

第1行三个整数n, m, T

接下来n行 ,每行三个整数xi, wi, ti为每种食物的份数xi,价值wi和吃每一份食物的时间ti,第i种食物位于魔法阵位置i

接下来m行,每行三个整数x, y, ti表示从位置x到位置y有一条消耗时间为ti的路(有向图,可能有多条从xy的路)。

1 ≤ n ≤ 100 , 1 ≤ m ≤ 5000 , 1 ≤ T ≤ 1000

1 ≤ xi ≤ 100, 1≤ wi ≤ 10^7, 1 ≤ ti ≤ T

1 ≤ x ≤ n, 1 ≤ y ≤ n

Output

输出一行 ,为瑶瑶在T时间内获得的最大价值。

Sample Input

3 5 10
1 1 1
3 2 4
1 10 5
0 1 1
0 2 5
0 3 1
1 2 1
2 3 1

Sample Output

11

Source

tsyao

Manager

Information
Solved Number149
Submit Number693
Problem Tags
dp
shortest paths
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel