Farmer John은 Cowribbean Sea의 섬 $N$개 $(1 \le N \le 100)$ 중 하나의 전설 보물을 배로 찾습니다. 번호는 $1,\ldots,N$입니다.

지도는1에서 출발해 $N$에서 끝나고 섬 $M$개 $(2 \le M \le 10,000)$의 순서 $A_{1}$, $A_{2}$, ..., $A_{M}$를 지나야 보물이 나타난다고 합니다. 이 섬과 다른 섬을 순서 밖으로 또는 반복 방문해도 되지만 지정 순서의 $A_{i}$를 포함해야 합니다.

FJ는 해적을 피하려 각 섬 쌍의 위험 $(0 \le danger \le 100,000)$를 압니다. 총 위험은 지나간 모든 경로의 위험 합입니다.

지도 조건을 만족하는 가장 안전한 보물 경로를 구하세요.

입력

• 1행: 공백으로 구분한 두 정수 $N$와 $M$.
• $2,\ldots,M+1$행: $i+1$행은 반드시 방문할 $i_{th}$번째 섬을 정수 $A_{i}$로 나타냅니다.
• $M+2,\ldots,N+M+1$행: $i+M+1$행의 공백으로 구분한 $N$개 정수는 섬 $i$에서1, 2, ..., $N$로 가는 위험입니다. $i$번째는 항상0입니다.

출력

• 1행: 보물을 얻는 최소 위험.

예제

입력 1

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

출력 1

7

참고

3섬에4방문은1, 2, 다시1, 마지막3입니다. (1,2), (2,3), (3,1)과 역방향의 위험은5, 2, 1입니다.

1, 3, 2, 3, 1, 3은 총7이며1, 2, 1, 3을 만족합니다. 위험이 큰1–2를 피합니다.

문제 작성자: Jeffrey Wang, 2007