Farmer John 决定给 $N$ 块草场（$1 \le N \le 300$，编号 $1,\ldots,N$）供水。可在该草场建井，或铺管连接到已有水的草场。

在草场 $i$ 挖井花 $W_i$（$1 \le W_i \le 100,000$）。管道连接 $i$、$j$ 花 $P_{ij}$（$1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$）。

求让所有草场有水的最少费用。

输入格式

• 第 1 行：整数 $N$。
• 第 $2,\ldots,N+1$ 行：第 $i+1$ 行含整数 $W_i$。
• 第 $N+2,\ldots,2N+1$ 行：第 $N+1+i$ 行有 $N$ 个空格分隔的整数，第 $j$ 个为 $P_{ij}$。

输出格式

• 第 1 行：一个整数，所有草场供水的最小费用。

样例

输入格式 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出格式 1

9

说明

四块草场：1 挖井花 5，2、3 花 4，4 花 3。连接不同草场的管道花 2、3 或 4。

可在第 4 块挖井，将各草场连接到第 1 块，花 $3+2+2+2=9$。

子任务

分值：400

题目作者：Paul Christiano，2007