在一个遥远的国家里有 $l$ 个城市，编号为 $0,1,\cdots,l-1$，围着一个大湖建成一圈。城市内和城市间有很多交通线路，并且它们都是双向的。
每个城市里都有 $n$ 个火车站，编号为 $0,1,\cdots,n-1$，由 $m$ 条动车线路相连。由于这些城市是一起修建的，所以任意两个城市内的火车站连接情况完全一致，即点集和边集都相等。
有些火车站是枢纽站。如果火车站 $s$ 在某个城市是枢纽站，那么所有城市的 $s$ 号火车站都是枢纽站。相邻城市的编号相同的枢纽站会被高铁线路连接。
一场天灾之后，所有这些线路都需要重建才可以被投入使用。由于城市之间非常相似，重建的费用也很有规律，具体如下：
- 每个城市 $i$ 都有两个正整数 $a_i,b_i$ 。
- 每条动车线路都有一个正整数 $d_j$ ，不同城市的同一条动车线路的 $d_j$ 相等。
- $i$ 号城市的 $j$ 号动车线路的重建费用是 $b_i+d_j$ 。
- $i$ 号城市和 $(i+1)\bmod l$ 号城市之间的任意一条高铁线路的重建费用都是 $a_i$ 。
你需要花费尽可能少的代价，重建若干条线路，使得国家里的任意两个火车站可以互达。
输入格式
第一行两个正整数 $n,m$ 。
接下来 $m$ 行，每行三个整数 $u_j,v_j,d_j$ ，描述一条连接 $u_j$ 和 $v_j$ 的动车线路。
接下来一行一个正整数 $l$ 。
接下来 $l$ 行，每行两个正整数 $a_i,b_i$ ，描述一个城市。
接下来一行一个正整数 $r$ ，表示一个城市里枢纽站的个数。
最后 $r$ 行，每行一个非负整数 $s_k$ ，表示每个城市的 $s_k$ 号火车站是枢纽站。
输出格式
一行一个正整数，表示使得所有火车站两两互达的最小代价。
样例一
input
2 1 0 1 3 3 6 1 4 2 5 3 1 1
output
24
样例二
input
3 3 0 1 7 1 2 8 2 0 5 4 8 1 5 1 9 3 7 3 2 1 2
output
76
样例三、四
见下发文件。
数据范围与提示
对于所有数据，$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$ ，图中无重边自环且连通，$s_k$ 两两不同。
| 子任务编号 | 特殊限制 | 分值 |
|---|---|---|
| $1$ | $n,l\le 10^3$ | $20$ |
| $2$ | $a$ 里不同的值的个数不超过 $20$ | $20$ |
| $3$ | $b$ 里不同的值的个数不超过 $20$ | $20$ |
| $4$ | $r\le 500$ | $20$ |
| $5$ | $ $ | $20$ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{1024MB}$