Mobile Service

A company provides service to customers located in different towns. The company has three service-staff employees. When a request occurs at some location, one employee must move from their current location to the location of the request in order to satisfy it, unless an employee is already there. Only one employee can move at any moment; employees move only in response to a request, and no two employees may occupy the same location.

Moving an employee from location $p$ to location $q$ costs a given amount $C(p, q)$. This cost function is not necessarily symmetric, but the cost of not moving is $0$, i.e. $C(p, p) = 0$. The company must satisfy the received requests in strict first-come, first-served order.

Decide which employee serves each request so that the total cost of serving the whole sequence of requests is as small as possible, and report that minimum total cost.

The first line contains two integers $L$ and $N$. $L$ ($3 \le L \le 200$) is the number of locations and $N$ ($1 \le N \le 1000$) is the number of requests. Locations are identified by the integers from $1$ to $L$.

Each of the next $L$ lines contains $L$ non-negative integers. The $j$-th number on line $i+1$ is the cost $C(i, j)$, which is less than $2000$.

The last line contains $N$ integers, the list of requests. Each request is given by the identifier of the location where it occurs. Initially, the three employees are located at locations $1$, $2$, and $3$, respectively.

Print a single integer $M$: the minimal total cost of serving the entire sequence of requests.