Задача №113639. Эстафета
Каждый год в честь дня города в Южно-Берляндске проводится открытая эстафета. В конкурсе участвуют команды из \(k\) человек, в процессе эстафеты участники команды должна посетить \(n\) контрольных пунктов.
Контрольные пункты пронумерованы от \(1\) до \(n\), место старта обозначим как пункт \(0\). Соревнование проходит следующим образом: первый участник из команды стартует из пункта \(0\), пробегает по некоторым \(a_1\) ранее не посещенным контрольным пунктам, возвращается в пункт \(0\) и передает эстафету второму участнику. После этого второй участник пробегает какие-либо \(a_2\) ранее не посещенных контрольных пунктов, возвращается и передает эстафету следующему. Эстафета продолжается, пока последний участник не посетит \(a_k\) ранее не посещенных контрольных пунктов и не вернется на старт. Передача эстафеты происходит мгновенно. Цель команды — пробежать эстафету как можно быстрее.
Учащиеся Южно-Берляндского бегового училища решили заранее подготовиться к состязанию. Они раздобыли план соревнования, из которого они узнали числа \(a_i\), а также выяснили про каждую пару пунктов, за какое время можно успеть добежать от одного до другого. Все участники команды перемещаются с одинаковой скоростью, поэтому это время не зависит от того, кто побежит между этими пунктами.
Помогите участникам составить маршрут, в котором команда пробежит эстафету как можно быстрее.
В первой строке находятся два целых числа \(n\) и \(k\) (\(1 \le n \le 18, \ 1 \le k \le n\)) — число контрольных пунктов и число участников в команде.
Во второй строке находятся \(k\) целых чисел \(a_i\) (\(1 \le a_i \le n, a_1 \ + \ a_2 \ + \ \dots \ + \ a_k \ = \ n\)) — число контрольных пунктов, которые должен пробежать \(i\)-й участник.
В следующих \(n \ + \ 1\) строках находится по \(n \ + \ 1\) целому числу \(b{i,\ j} \ (1 \le b_{i, \ j} \le 10^6, \ b_{i, \ j} \ = \ b_{j, i}, b_{i, \ i} \ = \ 0\)) — время, за которое можно добежать от \(i\)-го пункта до \(j\)-го для \(i\) и \(j\) от \(0\) до \(n\).
В единственной строке выведите одно целое число — минимальное время, за которое команда может пробежать эстафету.
2 2 1 1 0 1 2 1 0 3 2 3 0
6
4 2 2 2 0 1 4 2 5 1 0 2 6 6 4 2 0 6 6 2 6 6 0 2 5 6 6 2 0
16