O. The Martian
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Upon arriving on Mars, astronaut Mark Watney and his team discovered that the planet was not quite as they had expected. Its terrain was filled with large ravines—gaps in the ground—that made it very difficult for the team to traverse the red planet.

Fortunately, the astronauts brought along a set of ladders of various lengths; these ladders allowed them to cross the ravines when laid out horizontally, as long as their extended length was greater than or equal to the size of the gap.

The team has a schedule indicating one coordinate of interest to visit each day, and for these visits, they choose one ladder from their set to help cross the ravines. After reaching the point of interest, the astronauts must return via the same path they came from (back to the area where they reside), and the used ladder is then discarded due to wear and tear, making it unavailable for future days.

Given this, Mark was tasked with developing a program that, when provided with a map showing regions separated by ravines, the lengths of the ravines, the set of ladders brought by the team, and the cities the team wants to visit each day, maximizes the number of regions of interest visited during the entire mission. Mark, being a great biologist but not much of a programmer, called you for help.

The map of Mars is given as a graph with $$$N$$$ regions numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ ravines numbered from $$$1$$$ to $$$M$$$ connecting these regions, where the $$$i$$$-th ravine has a length of $$$w_i$$$ meters. It is also a fact that if it were possible to use a ladder of infinite length, one could travel from any region to any other region using only the ravines.

Additionally, the mission will last $$$D$$$ days, where the region to be visited on the $$$i$$$-th day is $$$d_i$$$, and the team has exactly $$$D$$$ ladders numbered from $$$1$$$ to $$$D$$$, where the length of the $$$i$$$-th ladder is $$$e_i$$$. Note that a ladder can be used on any day, but only once; and during a day, the chosen ladder can be reused as many times as necessary.

Knowing that the team resides in region $$$1$$$, write a program to help Mark's team with their mission!

Input

The first line of the input consists of two numbers $$$N$$$ and $$$M$$$ $$$(2 \le N \le 2 \cdot 10^5)$$$ $$$(1 \le M \le 2 \cdot 10^5)$$$, the number of regions and ravines on Mars, respectively.

The next $$$M$$$ lines each contain three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$, $$$(1 \le u_i, v_i \le N)$$$ $$$(1 \le w_i \le 10^9)$$$, indicating the existence of a ravine of length $$$w_i$$$ between regions $$$u_i$$$ and $$$v_i$$$. It is guaranteed that there is only one ravine connecting any two regions, and no ravine connects a region to itself.

Then, a line with a single integer $$$D$$$ $$$(1 \le D \le N)$$$ is given, representing the number of days in the mission; followed by two lines with $$$D$$$ integers each.

The first of these lines contains $$$d_1, d_2, \cdots, d_D$$$ $$$(1 \le d_i \le N)$$$, indicating that the $$$i$$$-th region to be visited is region number $$$d_i$$$.

The next line contains $$$e_1, e_2, \cdots, e_D$$$ $$$(1 \le e_i \le 10^9)$$$, indicating that the $$$i$$$-th ladder is $$$e_i$$$ meters long.

Output

Print a single line with the maximum number of regions that Mark and his team can visit.

Examples
Input
6 10
5 3 4
3 6 3
1 6 2
4 1 7
2 1 15
6 4 19
3 2 10
5 1 7
4 2 17
5 2 5
6
1 2 3 4 5 6
3 4 3 5 5 5
Output
5
Input
5 7
2 5 3
5 4 18
5 1 1
4 1 1
4 3 13
3 1 17
2 1 11
3
5 3 2
1 11 1
Output
2
Input
5 6
2 1 13
4 2 1
5 2 1
5 1 2
3 2 11
4 1 5
2
2 3
1 1
Output
0
Note

Below is the map for the second example:

We can use one of the ladders of length two to reach node $$$5$$$ on the first day; then, we can skip the second day's target and use the ladder of length $$$11$$$ to reach node $$$2$$$ on the third day (through the path 1 – 5 – 2). Note that there may be more than one way to achieve the optimal answer.