Description

Copy heard from Lu Niu that many treasures are buried in a divine land called yz, so Copy came to this land, which is divided into $n$ regions. Lu Niu told Copy that there are in total $P$ treasures, each placed in region $P_i$ ($1 \le P_i \le n$). Copy also learned the distance between every pair of regions. Now Copy starts from region $1$, wants to collect all treasures, and leave from region $n$. Copy is lazy, so he asks you to find a suitable route that minimizes the total distance he needs to travel.

Input Format

• The first line contains a positive integer $n$ ($1 \le n \le 100$).
• The next $n$ lines each contain $n$ integers; the number in row $i$, column $j$ denotes the distance from region $i$ to region $j$. The numbers are separated by spaces, and each distance is at most $1000$. Note that the distance $i \to j$ is not necessarily equal to $j \to i$.
• The next line contains an integer $P$ ($0 \le P \le 10$).
• The next line contains $P$ integers separated by spaces, denoting the indices of the regions that contain treasures.

Output Format

Output a single integer: the minimum total distance for Copy to collect all treasures and then reach region $n$. The testdata guarantees that the answer is at most $2^{31} - 1$.

2
0 4
5 0
2
1 2

4

3
0 2 6
1 0 4
7 10 0
1
2

6

Hint

• For $30\%$ of the testdata, $1 \le n \le 15$; the rest are as stated.
• For $100\%$ of the testdata, all constraints are as stated.

Translated by ChatGPT 5