DCMSF

Degree Constrained Spanning Forest(DCSF)는 양의 정수 $K$에 대해 모든 정점의 차수가 $K$ 이하인 Spanning Forest를 뜻한다. 그래프와 차수 제한 $K$가 주어졌을 때 이 조건을 만족하는 Degree Constrained Spanning Tree를 구하는 문제는 NP-Complete인 것으로 알려져 있다.

지수 시간이 걸리는 문제를 대회에 내고 싶지 않았던 정휘는, 새벽에 5시간 동안 고민한 끝에 여러 조건을 덧붙여 다항 시간에 풀 수 있는 문제를 만들었다.

정점 $N$개와 간선 $M$개로 이루어진 가중치 무방향 그래프가 주어진다. $X$개의 정점을 골라 특별한 정점으로, $Y$개의 정점을 골라 멋진 정점으로 지정한다. 다음 조건을 만족하는 Spanning Forest 중에서, 간선을 $1$개, $2$개, $\cdots$, $N-1$개 사용한 Spanning Forest의 간선 가중치 합의 최솟값을 각각 구해야 한다.

• $i$번째 특별한 정점의 차수는 $K_i$ 이하이다.
• 특별한 정점끼리는 서로 연결될 수 없다.
• 멋진 정점의 차수는 $1$ 이하이다.
• 멋진 정점끼리는 서로 연결될 수 없다.
• 한 정점이 특별한 정점이면서 동시에 멋진 정점일 수 있다.

첫째 줄에 $N$, $M$, $X$, $Y$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 300$, $1 \leq M \leq 300$, $1 \leq X, Y \leq N$)

둘째 줄에 특별한 정점의 목록 $A_1, A_2, \cdots, A_X$가 공백으로 구분되어 주어진다. ($1 \leq A_i \leq N$, $i \neq j$이면 $A_i \neq A_j$)

셋째 줄에 특별한 정점의 차수 제한 $K_1, K_2, \cdots, K_X$가 공백으로 구분되어 주어진다. ($1 \leq K_i \leq N$)

넷째 줄에 멋진 정점의 목록 $B_1, B_2, \cdots, B_Y$가 공백으로 구분되어 주어진다. ($1 \leq B_i \leq N$, $i \neq j$이면 $B_i \neq B_j$)

다섯째 줄부터 $M$개의 줄에 걸쳐 간선이 잇는 두 정점 번호 $u_i$, $v_i$와 간선의 가중치 $w_i$가 주어진다. ($1 \leq u_i, v_i \leq N$, $1 \leq w_i \leq 200000$, $u_i \neq v_i$)

같은 정점 쌍을 잇는 간선은 두 번 주어지지 않는다.

입력의 모든 수는 정수이다.

간선 $i$개로 조건을 만족하는 Spanning Forest를 만들 수 있다면 $i$번째 줄에 가중치 합의 최솟값을 출력한다.

간선 $i$개로 조건을 만족하는 Spanning Forest를 만들 수 없다면 $i$번째 줄에 $-1$을 출력한다.