Little D has an undirected weighted graph $G$ with $n$ vertices and $m$ edges, where the $i$-th edge connects $u_i$ and $v_i$ with weight $w_i$.

Little D also has two sequences $x$ and $y$ of length $k$, and a set $S \subseteq [0, n)$.

Little D constructs a new graph $H$ with a total of $nk$ vertices, where each vertex is represented by a pair $(a, b)$ with $a \in [0, k)$ and $b \in [0, n)$.

The edge set of the new graph $H$ consists exactly of the following types of edges: 1. For $a \in [0, k)$ and $i \in [0, m)$, there exists an edge connecting $(a, u_i)$ and $(a, v_i)$ with weight $w_i + y_a$. 2. For $a \in [0, k-1)$ and $i \in S$, there exists an edge connecting $(a, i)$ and $(a+1, i)$ with weight $x_a$. 3. For $i \in S$, there exists an edge connecting $(k-1, i)$ and $(0, i)$ with weight $x_{k-1}$.

Find the weight of the minimum spanning tree of graph $H$.

Input

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain three integers $u_i, v_i, w_i$.

The next line contains an integer $k$.

The next $k$ lines each contain two integers $x_i, y_i$.

The next line contains an integer $r$ representing the size of set $S$.

The next $r$ lines each contain an integer representing an element of set $S$.

Output

A single integer representing the weight of the minimum spanning tree.

Examples

Input 1

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

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
0
1

Output 2

76

Constraints

For all data, $1 \le n, m \le 10^5$, $2 \le k \le 10^5$, $0 \le u_i, v_i < n$, $0 \le w_i, x_i, y_i \le 10^8$, $1 \le r \le n$, $0 \le s_i < n$, $s_i$ are distinct, and $H$ is guaranteed to be connected.