스시스시 왕국

대학원생 호석이는 교수님의 호출에 화들짝 놀라 메다닥 달려가다가 넘어져 기절해버렸다. 호석이가 다시 눈을 떠 보니 이세계 스시스시 왕국의 왕이 되어 있었다.

스시스시 왕국에는 $N$개의 마을과 $M$개의 도시가 있다. 각 도시는 하나 이상의 마을로 이루어져 있으며, 같은 도시의 두 마을 사이에는 도로로 연결된 경로가 유일하게 존재한다. 그러나 서로 다른 도시에 속한 마을 간에는 직접 연결된 도로가 없다.

이제 스시스시 왕국은 새로운 도로를 건설하여 모든 마을을 오고 갈 수 있도록 연결하려고 한다. 도로는 두 마을을 직접 연결하며, 모든 도로의 길이는 $1$로 동일하다. 도로가 지나치게 많이 연결되면 두 마을을 오가는 여러 경로가 생겨 비효율적이므로, 도로를 건설한 후에도 두 마을 사이에는 도로로 연결된 경로가 유일하게 존재해야 한다. 하지만 각 도시의 행정관은 도로를 자기 도시 쪽으로 연결하기를 원하기 때문에 이를 만족하는 방법을 찾기란 쉽지 않다.

스시스시 왕국의 왕 호석이는 각 도시에 있는 마을에 $a_1$, $a_2$, $\cdots$, $a_M$개의 도로를 추가하도록 명령을 내렸다. 공평성을 위해 마을 수가 많은 도시일수록 연결할 도로의 수가 많거나 같도록 했다. 스시스시 왕국의 충신인 성재는 왕의 명령을 따르면서 모든 마을 사이의 거리의 합이 최소가 되도록 마을을 연결하려고 한다. 성재를 도와 마을 사이의 거리 합의 최솟값을 구해보자!

첫째 줄에 마을의 개수 $N$과 도시의 개수 $M$이 공백으로 구분되어 주어진다. $(2 \le M \le N \le 500\,000)$

둘째 줄에 각 도시에 추가로 연결되는 도로의 개수 $a_1$, $a_2$, $\cdots$, $a_M$이 공백으로 구분되어 주어진다. $(1 \le a_i < M;$ $\sum_i a_i =2(M-1))$

셋째 줄에 도시에 속하는 마을의 개수 $n_1$, $\cdots$, $n_M$이 공백으로 구분되어 주어진다. $(1 \le n_i \le N-M+1;$ $\sum_i n_i=N)$

넷째 줄부터 $N-M$개의 줄에 걸쳐 도로의 정보 $x_i$, $u_i$, $v_i$가 공백으로 구분되어 주어진다. 이는 도시 $x_i$에 속한 두 마을 $u_i$, $v_i$가 도로로 연결되어 있음을 의미한다. $(1 \le x_i \le M;$ $1 \le u_i, v_i \le N;$ $u_i \neq v_i)$

입력으로 주어지는 모든 수는 정수이다.

첫째 줄에 모든 마을 사이의 거리 합의 최솟값을 출력한다.