시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

출력

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

예제 입력 1

2 2
1 1
0 1 2
1 0 3
2 3 0

예제 출력 1

6

예제 입력 2

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

예제 출력 2

16