题目描述

给你一个 $\red{n }$个顶点的邻接矩阵（图），以及每个顶点的访问时限，要求从顶点 $\red{1 }$开始， 寻找一个访问序列，要求在每个顶点的访问时限之前访问，且每个顶点的访问时间之和最小。

输入格式

第一行一个数 $\red{n,2<=n<=30}$。

下面 $\red{n }$行为一个 $\red{n \times n }$的邻接矩阵，其中的第 $\red{i }$行第 $\red{j }$列元素值为顶点 $\red{i }$到顶点 $\red{j }$之间 的消耗时间（$\red{integer }$以内）。

最后一行为 $\red{n-1 }$个数（$\red{longint }$以内），分别表示第 $\red{2 }$到第 $\red{n }$个顶点的访问时限。

输出格式

一行一个数，表示按要求访问完所有顶点的最少时间。如果不能完成则输出一个$\red{-1}$。

样例

输入样例

4
0 3 8 6
4 0 7 4
7 5 0 2
6 9 3 0
30 8 30

输出样例

36