ADACITY  Ada and Cities
Ada the Ladybug and her friends are on trip in Bugraine. Most of them are in different cities at the moment. They want to spread as much as possible, make hologramskype to show all others the city. They have agreed, to make this call in time T.
The cities are connected with bidirectional roads. Each of the road has some length (which equals to time it takes to travel between two cities).
Input
The first line will contain the number of testcases.
The first line of each testcase begins with four integers: N,M,F,T, number of cities, number of roads, number of friends (Ada inclusive) and time they have: 1 ≤ N,F ≤ 500, 0 ≤ M ≤ 10^{5}, 0 ≤ T ≤ 5*10^{8}
Then a line with F integers follows, 1 ≤ H_{i} ≤ N, the city, where i^{th} friend currently is.
Afterward M lines follow, with three integers A,B,L, 1 ≤ A,B ≤ N, 1 ≤ L ≤ 10^{6}, indicating a road, which connect cities A,B with length of L
PS: There might exist multiple roads between two cities and there might also be a "circular route" which begins and ends in the same city!
Output
For each testcase, print maximal number of different cities Ada and her friends can end up at after T time!
Example Input
3 5 5 4 3 1 1 1 1 1 2 3 1 5 2 5 4 2 4 3 1 2 3 2 7 7 6 3 6 6 2 2 2 2 1 7 5 1 2 5 7 2 4 2 3 2 3 4 3 5 4 1 2 5 2 5 5 4 4 1 1 1 1 1 2 3 1 5 2 5 4 2 4 3 1 2 3 2
Example Output
3 5 4
Output Explanation
In first testcase, all 4 friends begin in same node. From this node, one can get to nodes 2 and 5, or stay in the node (in time ≤ 3). Since everyone is in node 1, best they can do is to choose one friend who goes to 5, one who goes to 2 and the rest of them can stay so with "1,1,2,5" they can occupy 3 different nodes (at most).
In second testcase, friends on 6 can go nowhere (just stay in 6). Friends on 2 can go to 3,4,5 or stay on 2. So with friends in 6,6,2,3,4,5 we get maximum of 5 different cities.
Last (third) testcase is same as first  except for time. This one additional timeunit will let friends go to 4 (or to nodes which they can go in first testcase). "1,2,4,5" would make 4 different cities!
hide comments
fuadul_hasan:
20220131 13:41:39
plz give me some idea to solve this problem.... I am getting wa several time. 

matheusdio:
20191003 18:47:47
Can anyone give me a tip? Because I don't know how to use maxflow in this question. 

Bojan Rosko:
20181127 20:18:27
The time limit is loose enough for any algorithm based on Ford Fulkerson method to pass (naive, Edmonds Karp, Dinic = Hopcroft Karp) 

the193thdoctor:
20180427 08:16:07
Finally AC with the magic O3 optimization 
Added by:  Morass 
Date:  20160918 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 