Эстафета

Каждый год в честь дня города в Южно-Берляндске проводится открытая эстафета. В конкурсе участвуют команды из $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 + \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$.

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