Рабочее место участника

Каждый год в честь дня города в Южно-Берляндске проводится открытая эстафета. В конкурсе участвуют команды из `k` человек, в процессе эстафеты участники команды должна посетить `n` контрольных пунктов.

Контрольные пункты пронумерованы от 1 до `n`, место старта обозначим как пункт 0. Соревнование проходит следующим образом: первый участник из команды стартует из пункта 0, пробегает по некоторым `a_1` ранее не посещенным контрольным пунктам, возвращается в пункт 0 и передает эстафету второму участнику. После этого второй участник пробегает какие-либо `a_2` ранее не посещенных контрольных пунктов, возвращается и передает эстафету следующему. Эстафета продолжается, пока последний участник не посетит `a_k` ранее не посещенных контрольных пунктов и не вернется на старт. Передача эстафеты происходит мгновенно. Цель команды – пробежать эстафету как можно быстрее.

Учащиеся Южно-Берляндского бегового училища решили заранее подготовиться к состязанию. Они раздобыли план соревнования, из которого они узнали числа `a_i`, а также выяснили про каждую пару пунктов, за какое время можно успеть добежать от одного до другого. Все участники команды перемещаются с одинаковой скоростью, поэтому это время не зависит от того, кто побежит между этими пунктами.

Помогите участникам составить маршрут, в котором команда пробежит эстафету как можно быстрее.

В первой строке находятся два целых числа `n` и `k` (`1\ ≤\ n\ ≤\ 18`, `1\ ≤\ k\ ≤\ n`) – число контрольных пунктов и число участников в команде.

Во второй строке находятся `k` целых чисел `a_i` (`1\ ≤\ a_i\ ≤\ n`, `a_1\ +\ a_2\ +\ …\ +\ a_k\ =\ n`) – число контрольных пунктов, которые должен пробежать `i`-й участник.

В следующих `n+1` строках находится по `n+1` целому числу `b_{i,j}` (`1\ ≤\ b_{i,\ j}\ ≤\ 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