건물주

강호는 구역 $N$개로 나뉜 도시의 건물주다. 구역에는 0번부터 $N-1$번까지 번호가 붙어 있고, 구역 사이는 양방향 도로로 이어져 있다.

강호가 소유한 차는 $C$대이고, 각 차는 구역 하나에 주차되어 있다. 한 구역에 여러 대가 주차되어 있기도 하다.

오늘은 월세를 받는 날이다. 강호는 자기 건물을 직접 돌아다니며 월세를 받는다. 월세를 받을 건물은 $M$개이고, 방문 순서는 $A_0, A_1, \dots, A_{M-1}$로 미리 정해져 있다. 먼저 $A_0$번 구역에서 월세를 받고, 다음으로 $A_1$번 구역에서 받고, 마지막으로 $A_{M-1}$번 구역에서 받는다. 강호는 처음에 0번 구역에 있다.

이동 방법은 걷기와 차 타기 두 가지다. 길이가 $L$인 도로를 걸어서 지나면 $W \times L$만큼 시간이 걸리고, 차로 지나면 $D \times L$만큼 시간이 걸린다.

자기 차가 주차된 구역에 도착하면 그 차 한 대에 타서 원하는 곳으로 이동할 수 있다. 한 번 내린 차에는 다시 타지 않는다. 또 월세를 받을 때는 반드시 차에서 내려야 한다.

도로 정보가 주어졌을 때, 월세를 모두 받는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 구역의 개수 $N$, 주차된 차의 개수 $C$, 월세를 받을 건물의 개수 $M$, 도로 길이 1당 걷는 데 걸리는 시간 $W$, 도로 길이 1당 차로 이동하는 데 걸리는 시간 $D$가 주어진다. ($1 \le N, C, M \le 50$, $1 \le D < W \le 100$)

둘째 줄에 차가 주차된 구역이 공백으로 구분되어 $C$개 주어진다.

셋째 줄에 월세를 받는 순서 $A_0, A_1, \dots, A_{M-1}$이 공백으로 구분되어 주어진다. ($A_0 \neq 0$)

넷째 줄부터 $N$개 줄에는 도시의 도로 정보가 인접 행렬 형식으로 주어진다. $i$번째 줄의 $j$번째 수는 $i$번 구역과 $j$번 구역 사이의 도로를 나타낸다. 0이면 도로가 없고, 자연수이면 그 도로의 길이다. 도로의 길이는 62 이하의 자연수다.

도로는 양방향이므로 $i$번째 줄의 $j$번째 수와 $j$번째 줄의 $i$번째 수는 항상 같고, $i$번째 줄의 $i$번째 수는 항상 0이다. 또, 어느 구역에서든 다른 모든 구역으로 갈 수 있다.

첫째 줄에 월세를 모두 받는 데 걸리는 시간의 최솟값을 출력한다.

첫 번째 예제에서는 구역 0에서 구역 2까지 걸어간 다음 월세를 받는다. 이어서 구역 2에서 3으로 걸어가 다시 월세를 받는다. 그다음 구역 1까지 걸어간 뒤 차를 타고 구역 0으로 가서 월세를 받는다. 걸린 시간은 $5 \times 1 + 5 \times 3 + 5 \times 2 + 1 \times 2 + 1 \times 3 + 1 \times 1 = 36$이다.

두 번째 예제에서는 구역 0에서 구역 1로 걸어간다. 거기서 차를 타고 구역 2로 이동한 뒤, 내려서 월세를 받는다. 그리고 구역 2에서 1을 거쳐 0까지 걸어간 다음 월세를 받는다. 걸린 시간은 $2 \times 37 + 1 \times 38 + 2 \times 38 + 2 \times 37 = 262$이다.