Kill The Monster

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 65536/32768KB (Java/Others)

Problem Description

Xxx正在玩一款游戏,游戏地图上有N个点,这些点之间有M条边。游戏系统会在一定时间在某点刷新出一定量的怪,系统刷新出来的怪只会存在1秒,下一秒就会消失。如果那个时间xxx正好在那个点,那么xxx可以秒杀这个点上的所有怪。另外,xxx还有B次放大招的机会,每次放大招可以秒杀掉当前所在点及与其相邻点上的所有怪。大招有5秒的冷却时间,也就是说每次放大后要经过5秒钟才能再次放大。Xxx想知道T时间内他最多可以杀掉多少只怪。Xxx可以从任意点开始。系统时间从1开始。

Input

输入的第一行包含一个整数CT(CT<=50), 表示一共有CT组测试数据。

对于每组测试数据,第一行包含5个整数N、M、T、K、B(1 <= N, T <= 50, 0<=M<= (N-1)*N/2, 0<=K<=10000, 0<=B<=5)。N、M、T意义如上所述,K表示有K个系统刷新。

接下来是M行,每行有3个整数u、v、t(1<=u, v<=N, u!=v, 1<=t<=10)表示从u走到v或者从v走到u需要花费t的时间。数据保证没有重边。

然后是K行,每行有3个整数t、p、c(1<=t<=50, 1<=p<=N, 1<=c<=100)表示t时间 在p点刷新出c个怪。

Output

对于每组测试数据,输出在T时间内xxx最多可以杀掉多少只怪。

Sample Input

2
5 4 3 9 2
1 2 1
2 3 2
2 4 1
2 5 1
1 1 2
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
3 3 5
3 4 1
3 5 1
5 4 6 8 2
1 2 1
2 3 2
2 4 1
2 5 1
1 1 1
1 2 1
4 3 1
6 1 1
6 2 1
6 3 1
6 4 1
6 5 1

Sample Output

18
8

Hint

第一组测试数据

第1秒,xxx在点1,普通攻击

点1走到点2

第2秒,xxx在点2,放大

点2走到点4

第3秒,xxx在点4,普通攻击

Source

zju_xxx

Manager

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