题目描述

HZY 雇佣了 $N$ 个标号为从 $1$ 到 $N$ 的间谍的情报机关的总管。每个间谍被派往不同的国家并在那获取重要情报。

如下是你的任务：

1．在部分间谍间组织会面。每次会面在两个间谍间进行，两个间谍交换他们自己获取的或从之前会面中得到的信息。因为在不同国家的两个间谍间组织机密会面很困难，所以每次秘密会面都有一个费用。

2．当所有会面结束后，选择一部分间谍参加拯救世界的任务。第 $i$ 个间谍参加此项任务需要花费 $M_i$。
​很重要的一点是，任务要成功，必须满足参加任务的间谍获取的情报聚集到一起包含了其他剩余间谍所有的信息。

请找出完成任务的最小花费，即组织会面和派遣间谍的费用之和。

输入

输入的第一行包含正整数 $N$，表示间谍数目（$2\le N\le1000$）。

接下来的 $N$ 行包含 $N$ 个不超过 $10^6$ 的非负整数。在 $i$ 行 $j$ 列的数字表示间谍 $i$ 和 $j$ 间会面的花费。如果 $i=j$，那么输入为 $0$。

接下来的一行包含 $N$ 个正整数 $M_k$（$1\le M_k\le10^6$），分别为派遣间谍 $1,2,⋯,N$ 参加任务的花费。

输出

只有一行，为所需的最小总费用。

样例

3
0 6 9
6 0 4
9 4 0
7 7 7

17

3
0 17 20
17 0 10
20 10 0
15 9 12

34

5
0 3 12 15 11
3 0 14 3 20
12 14 0 11 7
15 3 11 0 15
11 20 7 15 0
5 10 10 10 10

28