Watching butterflies unable to fly across the ends of the earth, who has the right not to understand?

An undirected graph together with two vertex sets $L$ and $R$ is called a butterfly graph if and only if the following conditions are satisfied:

• $L \cup R$ is the entire set of vertices.
• $L \cap R$ is non-empty.
• Any two vertices in $L$ can reach each other using only vertices in $L$.
• Any two vertices in $R$ can reach each other using only vertices in $R$.

Given a weighted butterfly graph, find a subset of edges with the minimum total weight such that the graph remains a butterfly graph after keeping only these edges.

Input

The first line contains four positive integers $n, m, l, r$, representing the number of vertices, the number of edges, and the sizes of $L$ and $R$, respectively.

The next $m$ lines each contain three positive integers $u, v, w$, representing an edge.

The next line contains $l$ positive integers representing the vertex set $L$.

The next line contains $r$ positive integers representing the vertex set $R$.

Output

Output a single positive integer representing the minimum total edge weight.

Examples

Input 1

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

Output 1

9

Input 2

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

Output 2

10

Subtasks

For $100\%$ of the data, it is guaranteed that $1 \le n \le 10^5$; $n - 1 \le m \le 2 \times 10^5$; $1 \le l + r - n \le 11$; $1 \le u, v \le n$; $1 \le w \le 10^9$, and the given graph together with sets $L$ and $R$ forms a butterfly graph.

For $50\%$ of the data, it is guaranteed that $n = 100$, and for the other $50\%$ of the data, it is guaranteed that $n = 10^5$.

Each part has 10 test cases, where the values of $l + r - n$ are $1, 3, 4, 5, 6, 7, 8, 9, 10, 11$, respectively.