계주

매년 도시의 날을 기념해 남부 베를랸츠크에서 공개 계주가 열린다. 대회에는 $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$). 이는 0부터 $n$까지의 $i$와 $j$에 대해 $i$번째 지점에서 $j$번째 지점까지 달리는 데 걸리는 시간이다.

한 줄에 팀이 계주를 완주하는 데 걸리는 최소 시간을 나타내는 정수 하나를 출력한다.