1294: 도시 건설 계획

N개의 도시가 있습니다. 각 도시는 0부터 N-1까지의 번호가 매겨져 있습니다. 도시들 사이에는 도로를 건설할 수 있으며, 각 도로는 특정 건설 비용을 가지고 있습니다. 당신의 목표는 모든 도시를 연결하면서 최소한의 비용으로 도로를 건설하는 것입니다. 단, 도시에 따라 특별한 조건을 만족해야 할 수도 있습니다.

몇몇 도시들은 "핵심 도시"로 지정될 수 있습니다. 핵심 도시들은 모두 연결되어야 하며, 핵심 도시들 간의 경로는 핵심 도시만을 통과해야 합니다. (핵심 도시가 아닌 도시를 경유하여 연결될 수 없습니다.) 또한, 핵심 도시가 아닌 도시들은 최소한 하나의 핵심 도시와 연결되어야 합니다.

주어지는 도로는 양방향이며, 도로의 개수는 매우 많을 수 있습니다. N은 최대 18입니다.

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 18)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 N개의 정수가 주어집니다.adj[i][j]는 도시 i와 도시 j를 연결하는 도로의 건설 비용을 나타냅니다. adj[i][i]는 항상 0입니다. 비용은 1 이상 1,000,000 이하의 정수입니다.

세째 줄에 핵심 도시의 개수 K (1 ≤ K ≤ N)가 주어집니다. 넷째 줄에 핵심 도시 K개의 번호가 공백으로 구분되어 주어집니다.

모든 조건을 만족하면서 모든 도시를 연결하는 최소 비용을 출력합니다.

4
0 10 20 30
10 0 5 15
20 5 0 25
30 15 25 0
2
0 2

30