//P2196 [NOIP1996 提高组] 挖地雷

#include<bits/stdc++.h>
#define  CLOSE ios::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
using namespace std;
using ll=long long;
typedef pair<int,int> PII;
const int N=1e6+10;
int n;
int w[50];
int  g[50][50];
ll ans;
int f[50];
bool st[5010];

int dfs(int u , int la)
{
    if (f[u])return f[u];
    int num = w[u];
    for (int i = 1;i <= n;i++)
    {
        if (!st[i]&&g[u][i])
        {
            st[i] = 1;
            num = max(num , dfs(i , u) + w[u]);
            st[i] = 0;
        }
    }
    f[u] = num;
    return num;
}

int main()
{
    CLOSE

        cin >> n;
    for (int i = 1;i <= n;i++)cin >> w[i];

    for (int i = 1;i <= n;i++)
    {
        for (int j = i + 1;j <= n;j++)
        {
            int c;cin >> c;
            g[i][j] = g[j][i] = c;
        }
    }

    for (int i = 1;i <= n;i++)
    {
        st[i] = 1;
        ans = max(ans , (ll)dfs(i , 0));
        st[i] = 0;
    }

    cout << ans;

    return 0;
}