In a distant country, there are $l$ cities, numbered $0, 1, \dots, l-1$, built in a circle around a large lake. There are many transportation lines within and between the cities, and all of them are bidirectional.

Each city contains $n$ train stations, numbered $0, 1, \dots, n-1$, connected by $m$ train lines. Since these cities were built together, the connectivity of train stations within any two cities is identical; that is, the sets of vertices and edges are the same.

Some train stations are hub stations. If a train station $s$ is a hub station in one city, then the station $s$ in all cities is a hub station. Hub stations with the same index in adjacent cities are connected by high-speed rail lines.

After a natural disaster, all these lines must be rebuilt before they can be put into use. Because the cities are very similar, the reconstruction costs follow a regular pattern, as follows:

• Each city $i$ has two positive integers $a_i$ and $b_i$.
• Each train line has a positive integer $d_j$, and the $d_j$ for the same train line in different cities is equal.
• The reconstruction cost of the $j$-th train line in city $i$ is $b_i + d_j$.
• The reconstruction cost of any high-speed rail line between city $i$ and city $(i+1) \bmod l$ is $a_i$.

You need to spend the minimum possible cost to rebuild a set of lines such that any two train stations in the country can reach each other.

Input

The first line contains two positive integers $n, m$.

The next $m$ lines each contain three integers $u_j, v_j, d_j$, describing a train line connecting $u_j$ and $v_j$.

The next line contains a positive integer $l$.

The next $l$ lines each contain two positive integers $a_i, b_i$, describing a city.

The next line contains a positive integer $r$, representing the number of hub stations in a city.

The last $r$ lines each contain a non-negative integer $s_k$, representing that station $s_k$ in each city is a hub station.

Output

A single positive integer representing the minimum cost to make all train stations mutually reachable.

Examples

Input 1

2 1
0 1 3
3
6 1
4 2
5 3
1
1

Output 1

24

Input 2

3 3
0 1 7
1 2 8
2 0 5
4
8 1
5 1
9 3
7 3
2
1
2

Output 2

76

Input 3, 4

See the provided files.

Constraints

For all data, $2 \le n \le 10^4, 1 \le m \le 10^5, 0 \le u_i, v_i, s_k < n, 1 \le d_j, a_i, b_i \le 10^9, 3 \le l \le 10^5, 1 \le r \le n$. The graph contains no multiple edges or self-loops and is connected. All $s_k$ are distinct.