Portal 3
题号：NC255863
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

What happened? Where is it? You wonder, waking up only to find yourself in a strange but familiar place. You look around, and the sign on the wall immediately reminds you where you are. The sign says “Aperture Science Enrichment Center”.

Hi Chell, glad to see you again. It is GLaDOS with her electronic voice. She seems excited to see you, You may wonder why you are here again. The truth is, after some failed trials, I finally realized that you are the one and only great test subject! Aperture Science needs you! You look frightened by her outburst. But she then goes back to a gentle, soft voice, Don't be afraid, all you need to do is complete some tests in some rooms, but this time you should make it as fast as possible. When all tests are done, you can have a cake as an award.


GLaDOS at the Aperture Science Enrichment Center


You don't know whether you can trust her, but you simply have no choice but to complete all tests as fast as possible. The Aperture Science Enrichment Center has n distinct rooms, labeled 1 through n. Thanks to recent developments in the years when you were absent, now you can directly go from any room i to room j (1\leq i,j\leq n) within time a_{ij}. You may assume that a_{i,i}=0 for all 1\leq i\leq n and a_{i,j}\geq 0 for all 1\leq i,j\leq n satisfying i\neq j. Also, as there exist one-way elevators, gels, companion cubes, and bots, it could happen that a_{i,j}\neq a_{j,i} for i\neq j. GLaDOS has handed you a list of rooms v_1,v_2,\dots,v_k (k\geq 2,1\leq v_i\leq n) so that you need to sequentially visit the rooms in the list in order, to complete all tests as fast as possible. You are now in room v_1 and are ready to take the first test at any time. As you are so familiar with all the tests, the time needed for you to complete each test can be ignored, and you only need to minimize the total time cost on the ways of visiting the rooms, which sounds easy enough.

Oh. I forgot to remind you, to make it easier for you but not too easy, you may look behind you. You turned around, and there is a portal gun in the box, but on the box, it says “Limited use: only use once before starting the tests”. With closer inspection, this portal gun creates portals not by shooting but by entering room numbers. The guideline lying next to it says that before trying to complete all tests, you are allowed to enter two numbers i,j such that 1\leq i\leq j\leq n, then a two-way portal will be created between rooms i and j, so that you can directly move from either one to the other within no time, meaning setting a_{i,j}=a_{j,i}=0. This choice of i and j needs to be made before trying to complete all the tests and cannot be changed.
So you need to carefully choose the two rooms to open up a portal, then complete all tests as quickly as possible. What is the minimum time needed? Surely you can find out.

输入描述:

The first line contains two integers n,k (2\leq n\leq 500,2\leq k\leq 10^6), denoting the number of rooms in the Aperture Science Enrichment Center and the length of the list containing the rooms to visit in order, respectively.

Then n lines follow, with the i-th (1\leq i\leq n) line containing n integers a_{i,1},a_{i,2},\dots,a_{i,n} (0\leq a_{i,j}\leq 10^9), describing the time needed to move directly from one room to another.

The last line contains k integers v_1,v_2,\dots,v_k (1\leq v_i\leq n), describing the sequence of rooms you need to visit in order.

输出描述:

Output one integer in a line, denoting the minimum time needed to complete all tests, after properly choosing a pair of rooms and setting up a two-way portal between them.
示例1

输入

复制 
3 4
0 4 2
3 0 6
5 1 0
1 2 3 1

输出

复制 
3
示例2

输入

复制 
4 10
0 1000000000 1000000000 1000000000
1000000000 0 1000000000 1000000000
1000000000 1000000000 0 1000000000
1000000000 1000000000 1000000000 0
4 3 2 1 3 2 4 1 2 3

输出

复制 
6000000000
示例3

输入

复制 
2 2
0 1
2 0
2 1

输出

复制 
0

备注:

To aid understanding, we provide graphical illustrations for the first sample test. The graph representing the Aperture Science Enrichment Center is given as follows.




If we open up a portal between rooms 1 and 2, the graph will become the following

Here the optimal route to complete all tests would be as follows: \textbf{1}\rightarrow \textbf{2}\rightarrow 1\rightarrow \textbf{3}\rightarrow 2\rightarrow \textbf{1}, taking a total amount of time equals to 0+0+2+1+0=3. Here the bold numbers correspond to the rooms in which you complete tests.


If we open up a portal between rooms 2 and 3, the graph will become the following

Here the optimal route to complete all tests would be as follows: \textbf{1}\rightarrow 3\rightarrow\textbf{2}\rightarrow \textbf{3}\rightarrow 2\rightarrow \textbf{1}, taking a total amount of time equals to 2+0+0+0+3=5.

If we open up a portal between rooms 1 and 3, the graph will become the following

Here the optimal route to complete all tests would be as follows: \textbf{1}\rightarrow 3\rightarrow\textbf{2}\rightarrow 1\rightarrow \textbf{3}\rightarrow \textbf{1}, taking a total amount of time equals to 0+1+3+0+0=4.

Overall, it's optimal to open a portal between rooms 1 and 2, and the minimum time needed to complete all tests equals 3.