UT Invitational Programming Contest Fall 2019

Start

2019-11-23 19:00 UTC

UT Invitational Programming Contest Fall 2019

End

2019-11-24 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -190 days 2:10:16

Time elapsed

5:00:00

Time remaining

0:00:00

Problem I
Pigeon X

$M$ bad pigeons in a mansion
Wrist on Milly Rock them diamonds on me dancin’
When you workin’ hard then your money start expandin’
I got model pigeon wanna peck me like some candy
And them seeds come in handy
Last name Savage pigeon, no I’m not Randy

$21$ Savage has $M$ bad pigeons in a mansion with $N$ rooms. Each pigeon is in a different room. He also has $M$ seed stashes stored in rooms across the mansion. The mansion can be represented as a weighted undirected graph where each room is a node and each corridor is an edge between two nodes. $21$ Savage desires to pair pigeons with a seed stash so that the total distance each pigeon has to travel to reach its seed is minimized.

Help $21$ Savage match pigeons with seed!

Input

The first line of input has two space separated integers $N$ and $M$, the number of rooms and the number of pigeons and seed stashes. It is guaranteed that $1 \le N \le 500$ and $1 \le 2M \le N$.

$N$ lines follow. Each line has $N$ space separated integers. The $j$th entry on the $i$th line represents the length of the corridor from room $i$ to room $j$. It is guaranteed that the length of the corridor from room $i$ to room $j$ is the same as the length of the corridor from room $j$ to room $i$. It is also guaranteed that the length of the corridor from room $i$ to room $i$ for all $i$ is $0$. Finally the lengths $l_{i,j}$ of the corridor between room $i$ and room $j$ satisfies $0 \le l_{i,j} \le 10\, 000$ for all $i$ and $j$.

The next line has $M$ space separated unique integers representing the room locations of the $M$ pigeons. It is guaranteed that all integers $F_ i$ satisfy $0 \le P_ i < N$.

The final line has $M$ space separated unique integers representing the room locations of the $M$ seed stashes. It is guaranteed that all integers $F_ i$ satisfy $0 \le F_ i < N$.

Output

Output a single integer, the minimum total distance that all pigeons have to travel to eat a unique seed stash.

Sample Input 1 Sample Output 1
4 2
0 2 2 2
2 0 2 2
2 2 0 2
2 2 2 0
0 1
2 3
4