Treasure Route with Sequence Constraint

Farmer John is on a boat seeking fabled treasure among \(N\) islands labeled \(1\) to \(N\). The treasure map specifies a sequence of islands \(A_1, A_2, \dots, A_M\) that must be visited in order, with \(A_1 = 1\) and \(A_M = N\). Although Farmer John can visit any islands (and even the same island more than once), his journey must contain the given sequence as a subsequence. Each path between two islands has an associated pirate-danger rating (an integer between 0 and 100,000), and the total danger rating is the sum of the dangers of all traversed paths.

Your task is to compute the minimum total danger rating of any route that satisfies the treasure map's requirements.

inputFormat

The input begins with a line containing two integers \(N\) and \(M\) (\(1 \le N \le 100\), \(2 \le M \le 10^4\)).

The second line contains \(M\) integers representing the required sequence \(A_1, A_2, \dots, A_M\). It is guaranteed that \(A_1 = 1\) and \(A_M = N\).

Then follow \(N\) lines, each containing \(N\) integers. The \(j\)th integer on the \(i\)th line denotes the pirate-danger rating from island \(i\) to island \(j\) (each rating is between 0 and 100,000 inclusive).

outputFormat

Output a single integer: the least total danger rating for a journey that includes the required sequence of islands.

sample

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

2