택시 합승

회사 직원 몇 명이 야근을 하다가 밤늦게 일을 마쳤다. 평소 대중교통을 이용하는 직원 $K$명($2 \le K \le 15$)이 택시 요금을 회사에서 부담해 달라고 관리자에게 요청했다. 택시는 얼마든지 부를 수 있으므로 관리자는 직원마다 택시를 한 대씩 잡아 줄 수도 있다. 그러나 그 방법은 너무 비싸다. 택시 한 대에는 1명부터 4명까지 탈 수 있고, 집이 가까운 사람끼리 같은 택시를 타면 요금이 훨씬 싸다. 한편 택시가 동료를 먼저 내려 주고 되돌아와 나머지를 태우는 동안 직원을 밖에서 기다리게 하는 것은 예의가 아니라고 관리자는 판단했다. 그래서 관리자는 다음 조건을 지키면서 모든 직원을 집까지 데려다주는 가장 싼 방법을 고르려고 한다.

• $K$명을 그룹으로 나눈다. 각 그룹의 인원은 1명, 2명, 3명, 4명 중 하나이고, 어떻게 묶을지는 관리자가 정한다.
• 같은 그룹에 속한 직원은 택시 한 대를 함께 탄다.
• 그룹은 회사에서 출발해 구성원 중 한 명의 집으로 가고, 그 사람이 내린다. 남은 사람이 있으면 다음 사람의 집으로 가고, 이런 식으로 계속한다. 누구의 집에 몇 번째로 갈지도 관리자가 정한다.
• 관리자는 $K$명에 포함되지 않고 어느 그룹에도 속하지 않는다. 자기 차를 몰고 가며 직원을 태우지 않는다.

회사와 직원의 집은 가중치 그래프의 정점에 있다. 그래프의 간선은 대부분 무향(양방향 도로)이지만 일부는 유향(일방통행)일 수 있다. 각 간선의 가중치는 그 간선을 택시로 지날 때 내는 요금이다. 그래프는 강한 연결 그래프이다. 즉, 어느 정점에서든 다른 어느 정점으로도 가는 경로가 있다. 택시 요금은 거리 요금과 기본요금으로 나뉜다. 기본요금은 이동 거리나 승객 수와 관계없이 택시 한 대마다 한 번씩 붙는다.

첫째 줄에 정점의 개수 $N$($5 \le N \le 20000$)과 간선의 개수 $M$($N \le M \le 50000$)이 주어진다.

이어지는 $M$개의 줄에는 각각 네 정수가 주어진다. 첫 번째 수는 1 또는 2이고, 1이면 일방통행 도로, 2이면 양방향 도로이다. 다음 두 수 $u$, $v$($u \ne v$, $1 \le u \le N$, $1 \le v \le N$)는 도로가 잇는 두 정점이며, 일방통행이면 $u$에서 $v$로 향한다. 네 번째 수는 그 도로를 택시로 지날 때 내는 요금이고 5 이상 5000 이하이다.

다음 줄에는 기본요금이 주어진다. 500 이상 50000 이하의 정수이다.

다음 줄에는 회사가 있는 정점의 번호가 주어진다. 1 이상 $N$ 이하이다.

다음 줄에는 직원 수 $K$($2 \le K \le 15$)가 주어진다.

마지막 줄에는 직원이 사는 정점의 번호 $K$개가 주어진다. 각 번호는 1 이상 $N$ 이하이다. 두 직원이 같은 정점에 살 수도 있지만, 회사가 있는 정점에 사는 직원은 없다.

모든 직원을 집까지 데려다주는 데 드는 최소 총비용을 한 줄에 출력한다.

첫 번째 예제에서는 택시 한 대가 직원 네 명을 모두 태우고 2번 직원의 집, 1번 직원의 집, 4번 직원의 집, 3번 직원의 집 순서로 가면 최소 비용 4500이 나온다. 두 번째 예제에서는 택시 두 대를 쓰면 최소 비용 3700이 나온다. 한 대는 1번 직원의 집에 들른 뒤 2번 직원의 집으로 가고, 다른 한 대는 3번 직원의 집에 들른 뒤 4번 직원의 집으로 간다.