첩보원

당신은 정보기관의 수장 M이며, 1번부터 N번까지의 암호명을 가진 N명의 첩보원을 거느리고 있습니다. 각 첩보원은 서로 다른 나라에 파견되어 그곳에서 중요한 정보 한 가지씩을 입수했습니다.

당신이 해야 할 일은 두 단계로 이루어집니다.

1. 첩보원들 사이의 회동을 주선합니다. 한 번의 회동에서는 정확히 두 명의 첩보원이 만나, 자신이 직접 얻었거나 이전 회동에서 알게 된 모든 정보를 서로 교환합니다. 서로 다른 나라에 있는 두 첩보원의 비밀 회동을 주선하는 일은 까다롭기 때문에, 가능한 각 회동에는 정해진 비용이 있습니다.
2. 모든 회동이 끝난 뒤, 첩보원 중 일부를 골라 함께 임무에 파견합니다. 첩보원 $k$를 파견하는 데는 $M_k$의 비용이 듭니다. 파견된 첩보원들이 함께, 파견되지 않은 첩보원들이 원래 입수한 모든 정보를 알고 있어야만 임무가 성공합니다.

임무를 준비하고 수행하는 데 드는 최소 총비용(주선한 회동들의 비용 합과 파견한 첩보원들의 파견 비용 합)을 구하세요.

첫째 줄에 첩보원의 수 $N$이 주어집니다 ($2 \le N \le 1000$).

다음 $N$개의 줄에는 각각 $N$개의 정수가 주어집니다. $k$번째 줄의 $m$번째 정수는 첩보원 $k$와 $m$의 회동 비용이며, $m$번째 줄의 $k$번째 정수와 같고, 대각선 위치($k = m$)의 값은 $0$입니다. 모든 회동 비용은 $10^6$ 이하의 양의 정수입니다.

마지막 줄에는 $N$개의 정수 $M_1, M_2, \ldots, M_N$이 주어집니다 ($1 \le M_k \le 10^6$). $M_k$는 첩보원 $k$를 임무에 파견하는 비용입니다.

최소 총비용을 정수 하나로 출력합니다.

첫 번째 예제에서는 첩보원 1과 2, 그리고 2와 3 사이의 회동을 주선한 뒤 첩보원 2를 파견합니다.

두 번째 예제에서는 첩보원 2와 3 사이의 회동을 주선한 뒤 첩보원 1과 2를 파견합니다.

세 번째 예제에서는 첩보원 2와 4, 이어서 1과 2, 그리고 3과 5 사이의 회동을 주선한 뒤 첩보원 1과 3(또는 1과 5)을 파견합니다.