丞相诸葛亮治理蜀地时，发现各城池水源匮乏。他决定通过两种方式解决供水问题：

在城池中建造水井，或在城池间修建运河连通水源。已知在第 i 座城池建造水井需耗费 W_i 斛粮草，连接 i 城与 j 城的运河需耗费 P_{i,j} 斛粮草（P_{j,i}=P_{i,j}）。

请帮丞相计算，使所有城池都与水源连通（或自有水井）的最小粮草耗费。

第一行：整数 n（蜀地共有 n 座重要城池）

接下来 n 行：每行一个整数 W_i（在 i 城打井的粮草耗费）

接下来 n 行：每行 n 个整数，第 i 行第 j 个数为 P_{i,j}（i 城与 j 城修运河的耗费）

最少的粮草耗费

样例解释：最优方案：江州打井(3)，连接成都-汉中(2)、成都-梓潼(2)、成都-江州(2)，总耗费3+2+2+2=9

对于 100\% 的数据，1 \leq n \leq 300，1 \leq W_i \leq 10^5，0 \leq P_{i,j} \leq 10^5。