Fly or not fly#3789
Welcome to Mars! Your first mission is to send letters to cities A_1, A_2, …, A_K in order. Mars consists of cities connected by roads, different roads may have different lengths, in city there are P_i UFOs which you can take to increase your speed, let's assume that the road's length is , so if you walk through this road, you'll spend minutes, but if you fly (by UFO of course), you'll only spend minutes. However, you must have this mission done in minimal time, and each UFO can only be used once, it disappears when you leave it, you can't send letters when you are in the UFO, so you must leave it in order to send a letter.
There are several test cases, end with EOF. For each test case, the first line contains two integers N \le 100, and K \le N, the second line is integers, P_1, P_2, …, P_N.(P_i \le 10), Next lines is an N \times N matrix G_{1..N,1..N} for the lengths between every two cities(G_{i,j} \le 100), it is guaranteed that G_{i,j}=G_{j,i} and G_{i,i}=0, if G_{i,j}=-1, it means that there is no road between city and . The last line of each case is integers A_1, A_2, …, A_K. You are in city A_1 at first.
For each case, output the minimal time.
Παράδειγμα 1