Clear and Present Danger

Farmer John is sailing in search of legendary treasure hidden on one of $N$ islands, conveniently numbered $1$ through $N$ ($1 \le N \le 100$).

The treasure map tells him that, before the treasure will appear, he must travel through a sequence of $M$ islands $A_1, A_2, \ldots, A_M$ ($2 \le M \le 10000$) in the given order. The route starts at island $1$ and ends at island $N$ (that is, $A_1 = 1$ and $A_M = N$). He may stop at other islands along the way and may visit the same island more than once, but he must visit $A_1, A_2, \ldots, A_M$ in exactly this order.

Farmer John wants to avoid pirates and knows the pirate-danger rating $d$ ($0 \le d \le 100000$) between every pair of islands. The total danger of a route is the sum of the danger ratings of every segment he travels.

Help Farmer John find the least dangerous route that satisfies the treasure map's requirement, and report its total danger.

• Line 1: Two space-separated integers $N$ and $M$.
• Next $M$ lines: line $i$ contains a single integer $A_i$, the $i$-th island Farmer John must visit ($A_1 = 1$, $A_M = N$).
• Next $N$ lines: line $i$ contains $N$ integers; the $j$-th integer is the danger rating of the path between island $i$ and island $j$. The $i$-th integer on line $i$ is always $0$.

• A single integer: the minimum total danger Farmer John must encounter to obtain the treasure.

You do not have to travel directly between two consecutive required islands — routing through other islands can be safer. For example, going directly between island $1$ and island $2$ has danger $5$, but the route $1 \to 3 \to 2$ costs only $1 + 2 = 3$. Using the safest path between each consecutive required pair ($1 \to 2$, $2 \to 1$, $1 \to 3$) gives a total danger of $3 + 3 + 1 = 7$.