在一个远离大陆的火山小岛上，无痛骑行大理事会（Grand Council for Painless Cycling, GCPC）经常收到关于自行车道网络质量差的投诉。他们的预算有限，但他们希望改善岛上所有骑行者的出行状况。一项调查帮助确定了骑行者最常去的目的地。GCPC 认为，如果可以通过仅使用新更换的自行车道在任意两个目的地之间骑行，骑行者就会对自行车道的更换感到满意。为了不偏袒任何一个村庄，理事会决定每个村庄最多考虑 7 个目的地。

图 I.1：第二个样例的示意图。村庄 1 由路口 1, 2, 3 和 4 组成，村庄 2 仅由路口 5 组成，村庄 3 由其余路口组成。作为目的地的路口被染成红色。

有一条环绕火山的主要环形自行车道。在它的路径上，它恰好穿过岛上的每个村庄一次。每个村庄可能还有额外的自行车道。GCPC 至少需要花费多少资金来更换自行车道，以便通过新车道连接所有目的地？

输入格式

输入包含以下内容：

• 第一行包含四个整数 $n, m, v$ 和 $k$（$3 \le n \le 5000$，$n \le m \le 20\,000$，$3 \le v \le n$，$1 \le k \le n$），分别表示路口数量、自行车道数量、村庄数量和目的地数量。
• 第二行包含 $v$ 个整数 $u_i$（$1 \le u_i$，$\sum_{i=1}^v u_i = n$），其中第 $i$ 个整数表示村庄 $i$ 中的路口数量。
• 接下来 $m$ 行，每行包含三个整数 $a, b$ 和 $c$（$1 \le a, b \le n$，$1 \le c \le 10^9$），描述一条连接路口 $a$ 和路口 $b$ 的双向自行车道，其更换成本为 $c$。
• 最后一行包含 $k$ 个互不相同的整数 $t$（$1 \le t \le n$），表示必须通过更换后的自行车道连接的目的地路口。

此外，保证满足以下条件：

• 村庄 1 由路口 $1, \dots, u_1$ 组成，村庄 2 由路口 $u_1+1, \dots, u_1+u_2$ 组成，依此类推。最后一个村庄由路口 $1 + \sum_{i=1}^{v-1} u_i, \dots, n$ 组成。在每个村庄内部，可以在不离开该村庄的情况下在任意一对路口之间通行。
• 对于每个 $1 \le j \le v - 1$，在路口 $\sum_{i=1}^j u_i$ 和 $1 + \sum_{i=1}^j u_i$ 之间存在一条自行车道，且在路口 $n$ 和 $1$ 之间也存在一条自行车道。不同村庄之间没有其他自行车道。
• 每对路口之间最多只有一条自行车道，且没有自行车道连接路口自身。
• 在每个村庄中，最多有 7 个路口需要成为改进后的骑行网络的一部分（即目的地）。

输出格式

输出允许更换自行车道的最小成本，使得任意两个目的地之间的每一次出行都可以仅通过新更换的车道完成。

样例

输入样例 1

3 3 3 3
1 1 1
2 1 5
2 3 4
1 3 3
2 1 3

输出样例 1

7

输入样例 2

8 10 3 6
4 1 3
1 2 3
2 4 2
1 3 5
3 4 2
4 5 3
5 6 2
8 6 3
6 7 2
7 8 2
8 1 1
2 3 1 7 6 8

输出样例 2

12