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 hologram-skype to show all others the city. They have agreed, to make this call in time T.

The cities are connected with bi-directional 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 test-cases.

The first line of each test-case 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 ≤ 105, 0 ≤ T ≤ 5*108

Then a line with F integers follows, 1 ≤ Hi ≤ N, the city, where ith friend currently is.

Afterward M lines follow, with three integers A, B, L, 1 ≤ A, B ≤ N, 1 ≤ L ≤ 106, 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 test-case, 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 test-case, 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 test-case, 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) test-case is same as first - except for time. This one additional time-unit will let friends go to 4 (or to nodes which they can go in first test-case). "1, 2, 4, 5" would make 4 different cities!


Added by:Morass
Date:2016-09-18
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2022-01-31 13:41:39
plz give me some idea to solve this problem.... I am getting wa several time.
2019-10-03 18:47:47
Can anyone give me a tip? Because I don't know how to use max-flow in this question.
2018-11-27 20:18:27 Bojan Rosko
The time limit is loose enough for any algorithm based on Ford Fulkerson method to pass (naive, Edmonds Karp, Dinic = Hopcroft Karp)
2018-04-27 08:16:07
Finally AC with the magic O3 optimization
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.