Летіти чи не летіти
Ласкаво просимо на Марс! Ваше перше завдання — доставити листи до K міст A_1, A_2, …, A_K у заданій послідовності. Марс складається з N міст, з'єднаних дорогами, причому довжина доріг може відрізнятися. У місті i є P_i НЛО, які ви можете використати для збільшення швидкості. Якщо довжина дороги становить x, то пішки ви витратите 5x хвилин, а на НЛО — лише x хвилин. Однак, ваше завдання — виконати це за мінімальний час, причому кожне НЛО можна використати лише один раз, і воно зникає, коли ви його залишаєте. Ви не можете відправити листи, перебуваючи в НЛО, тому повинні залишити його, щоб відправити лист.
Вхідні дані
Є кілька тестових випадків, які закінчуються на EOF. Для кожного тестового випадку перший рядок містить два цілі числа N ≤ 100 і K ≤ N. Другий рядок містить N цілих чисел P_1, P_2, …, P_N (P_i ≤ 10). Далі йдуть N рядків, які утворюють N×N матрицю G_{1..N,1..N}, що описує довжини між кожними двома містами (G_{i,j} ≤ 100). Гарантується, що G_{i,j}=G_{j,i} і G_{i,i}=0. Якщо G_{i,j}=-1, це означає, що дороги між містами i та j немає. Останній рядок кожного випадку містить K цілих чисел A_1, A_2, …, A_K. Спочатку ви знаходитесь у місті A_1.
Вихідні дані
Для кожного випадку виведіть мінімальний час.