问题描述

大草原上有N个蒙古包，各蒙古包可以建立自己的太阳能发电站，也可以通过建设供电线路，从其他蒙古包取电。也就是说，一个发电站集中供电或者各自分散建立发电站都可能不是最优的选择。既有集中供电，也有分散发电可能才是最好的选择。给定各蒙古包建设太阳能发电站的造价和到其他蒙古包取电所建设线路造价，求满足所有蒙古包供电需求的集散供电系统的最小造价。

输入格式

第一行，一个正整数N，草原上蒙古包的数量。

第二行N个整数，表示各蒙古包单独建设太阳能发电站的造价。

以下是N×N的矩阵T，T~uv~表示第u个蒙古包和第v个蒙古建设供电线路的造价。

输出格式

一个整数，表示满足所有蒙古包供电需求的供电系统的最小造价。

输入样例

4

5 6 4 4

0 2 2 2

2 0 4 4

2 4 0 3

2 4 3 0

输出样例

10

数据范围

1<=N<=1000

提示说明

在第4个蒙古包建发电站，其它不建，而是通过建设输电线路供电，成本为4+2+2+2=10。