Treasure Diving#3783
Legends often tell of great treasures. But you rarely get the chance to actually stumble upon those treasures. Most of them are lost in the sea, or hidden below mountains. But as you learned from one of your biggest idols, treasures do belong in a museum. And now you have the chance to make that happen.
On an expedition, you found a large cave network. A native shaman has spoken about incredible values his ancestors have hidden in the caves. He even gave you an ancient map, depicting the cave network and the location of the treasures within. Sadly, the cave network is completely flooded. Since the trip out here takes forever, you decided to do a short dive and scout out the cave network. But on your arrival back at the entrance to the cave network you get the news... a volcano just erupted nearby. It is almost guaranteed that the lava will cover the entries to the cave network and the treasures will be lost forever.
That puts you on the spot. You only have a short time left, and only one lousy tank of air. So it is all on you. You only have time for a single dive. But how could you possibly decide which route to take? The cave network is huge, and you should definitely try and rescue as much of the treasures as possible. You think back to your times as a computer scientist at the university... And then it hits you. You still have your laptop with you. You could write a program to help you figure out the best you can do in rescuing the treasures.
You may assume that neither locating nor picking up a treasure within a cave nor the traversal of a cave consumes any air.
Each test set consists of multiple test cases. The file starts with a single number (0 < t \leq 2000) on a single line, denoting the number of test cases in the file. Each test case starts with two integers and on a single line, where is the number of caves and is the number of connecting tunnels in the network (1 \leq n \leq 10000, 0 \leq m \leq 50000). This line is followed by lines, giving a description of the tunnels of the cave as three integers , and with , denoting caves and giving the amount of air necessary for diving through the tunnel (0 \leq a, b < n, 0 \leq l \leq 500). After the tunnels follows an integer on a single line, giving the number of idols in the cave system (0 \leq i \leq 8). This line is followed by a single line containing integers p_1, \ldots, p_i giving the caves within the network containing an idol (0 \leq p_1, \ldots, p_i < n). The input is concluded by a single number, giving the liters of air you have available (0 \leq a \leq 1000000). You will always start (and end) at the node with the label .
For each test case print a number on a single line, where is replaced by the maximal number of idols the diver can recover.
Example 1