#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 #define eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int maxn = +;

 const int mod = 1e9+;

 int dis[][],deadline[];

 int vis[];

 int n,ans;

 void dfs(int u, int cnt, int time, int sum)

 {

     if(cnt==n)

     {

         ans = min(ans,sum);

         return;

     }

     //剪枝：

     if(sum+time*(n-cnt)>=ans) return;

     for(int i = ; i<=n; i++)

         if(!vis[i] && time+dis[u][i]>deadline[i]) return;

     for(int i = ; i<=n; i++)

     {

         if(!vis[i])

         {

             vis[i] = ;

             dfs(i,cnt+,time+dis[u][i], sum+time+dis[u][i]);

             vis[i] = ;

         }

     }

 }

 void solve()

 {

     for(int i = ; i<=n; i++)

         for(int j = ; j<=n; j++)

             scanf("%d",&dis[i][j]);

     for(int i = ; i<=n; i++)

         scanf("%d",&deadline[i]);

     for(int k = ; k<=n; k++)//弗洛伊德算法

         for(int i = ; i<=n; i++)

             for(int j = ; j<=n; j++)

                 dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);

     ans = INF;

     ms(vis,);

     dfs(,,,);

     if(ans!=INF)

         printf("%d\n",ans);

     else

         puts("-1");

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF){

         solve();

     }

     return ;

 }