\begin{problem}{Эстафета}{run.in}{run.out}{2 секунды}{256 мегабайт}
                                                                    
%Автор задачи: Васильев Артем
%Автор условия: Збань Илья

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

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

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

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


\InputFile
В первой строке находятся два целых числа $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 + \ldots + 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$.

\OutputFile
В единственной строке выведите одно целое число~--- минимальное время, за которое команда 
может пробежать эстафету.

\Example
\begin{example}%
\exmp{
2 2
1 1
0 1 2
1 0 3
2 3 0
}{
6
}%
\exmp{
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
}%
\end{example}

\end{problem}