Description

Farmer John已经决定把水灌到他的 \(n(1 \leq n \leq 300)\) 块农田, 农田被数字1到 \(n\) 标记。把一块土地进行灌水有两种方法, 从其他农田饮水, 或者这块土地建造水库。建造一个水库 需要花费 \(w_{i}\left(1 \leq w_{i} \leq 10^{5}\right)\) ，连接两块土地需要花费 \(\operatorname{Pij}\left(1 \leq P_{i j} \leq 10^{5}, P_{i j}=P_{j i}, P_{i i}=0\right)\)。 计算Farmer John所需的最少代价。

输入格式

第一行: 一个数 \(n\)
第二行到第 \(n+1\) 行：第 \(i+1\) 行含有一个数 \(w_{i}\)
第 \(n+2\) 行到第 \(2 * n+1\) 行：第 \(n+1+i\) 行有 \(n\) 个被空格分开的数，第 \(j\) 个数代表 \(p_{i j}\) 。

输出格式

一个单独的数代表最小代价.

样例

输入

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

输出

9

数据范围与提示

输出详解: Farmer John在第四块土地上建立水库, 然后把其他的都连向那一个, 这样就要花费 \(3+2+2+2=9\)