Description

小$A$潜入了墓室中的一个房间，他发现房间里有$n$个宝物，每个宝物都有一个重量$v[i]$,且每两个宝物之间有一个关联度$w[i,j]$。如果某个时刻还没有被偷走的宝物的集合为$S$,此时拿走宝物i需要能量∑j∈s vi*wi,j 小A希望偷走所有的宝物，但是他力量有限，所以希望求得偷走所有宝物需要的最小能量和。

Input Format

第一行一个整数，表示宝物的个数n,

第二行n个整数，第i个数表示第1个宝物的重量vi,

接下来n行，每行n个整数，第i行第j列表示宝物i与宝物j的关联度Wi,j 保证对角线上是0,

不保证重量与关联度为非负数。

Output Format

一个整数，表示小A偷走所有宝物需要的最小能量和。

Sample

Input

4
2 5 1 7
0 343 154 12
343 0 214 132
154 214 0 441
12 132 441 0

Output

2179

Hint

Hint

Source

2019泉州市基地校活动提高组day1