시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

One facility and several clients are located in some vertices of a weighted graph G = (V, E). Each client j has some nonnegative demand dj and a nonnegative priority value pj that indicates the importance of that client. The servicing cost of a client j is cj ⋅ dj , where cj is the shortest distance of j from the facility vertex in graph G to a client j . For example, in the figure below, the servicing cost of the client a is a 3⋅da, where da is the demand of the client a. The servicing cost of the client b in the figure is infinite because the there is no path from the client b to the facility in the given graph.

You have to write a program that selects a subset of the client set such that total servicing cost of all the clients in this subset is bounded by a nonnegative budget B and the total priority value of all clients in this subset is maximized. 

입력

Your program is to read from standard input. The input consists of T (1 ≤ T ≤ 20) test cases. The value of T is given in the first line of the input. Each test case starts with a positive integer N (1 ≤ N ≤ 100) indicating the number of vertices in the graph. You can assume that the vertices are numbered from 0 to N – 1 and vertex 0 contains the facility. The next line contains an integer M (0 ≤ M ≤ 100) indicating the number of clients. Next M lines contain the description of each client. Each line contains three integers – vertex index, demand and priority value of the client. Each integer has ranges of [0,100]. After the description of M clients, the next line contains an integer B (0 ≤ B ≤ 100) indicating the total budget. The next line contains an integer L (0 ≤ L ≤ 100) indicating the number of edges. Next L lines describe the edges. Each line contains three integers – first two integers indicate the two vertices incident to the edge and the third integer indicates its cost. Again each integer is within the range of [0,100]. 

출력

Your program is to write to standard output. Print exactly one line for each test case with the total priority value of the clients selected for the service. 

예제 입력 1

2
4
4
1 5 7
2 35 20
3 12 32
3 10 2
30
5
0 1 5
0 2 4
1 3 13
2 3 4
1 2 2
6
6
1 3 4
1 2 4
3 4 5
3 2 1
4 6 3
5 1 2
20
8
0 1 3
1 2 5
2 3 3
3 4 5
4 5 10
0 5 4
0 3 4
2 5 6

예제 출력 1

7
10

힌트