Pigeon X

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!

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 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 |