#include <bits/stdc++.h>

using namespace std;

#define ll long long // 定义长整型
#define pii pair<int, int> // 定义一个整数对
#define pb push_back // 简化向容器添加元素的操作

const int M = 605; // 定义最大任务数量
int in[M], a[M]; // in数组存储每个任务的入度，a数组存储每个任务的内存需求
vector<int> e[M]; // 使用邻接表表示依赖关系图

int main() {
    int n, t; // n表示任务数量，t用于读取依赖关系
    cin >> n; // 输入任务数量
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i); // 输入每个任务的内存需求
    }
    // 读取任务间的依赖关系
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &t);
            if (t) {
                in[i]++; // 增加任务i的入度
                e[j].pb(i); // 记录有一条从任务j到任务i的依赖边
            }
        }
    }
    
    queue<int> q, tmp; // q保存当前入度为0的任务，tmp用于保存下一轮的任务
    // 将所有入度为0的任务加入队列
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) q.push(i); // 加入初始任务
    }
    
    int ans = 0; // 用于记录最大内存消耗
    while (!q.empty()) { // 当队列不为空时，说明还有可执行的任务
        int sum = 0; // 当前轮次内存消耗总和
        while (!q.empty()) { // 处理当前轮次所有入度为0的任务
            int u = q.front(); // 获取队头任务
            q.pop(); // 从队列中移除该任务
            sum += a[u]; // 累加内存消耗
            // 遍历所有依赖于任务u的任务
            for (int i = 0; i < (int)e[u].size(); i++) {
                in[e[u][i]]--; // 将依赖于u的任务的入度减1
                if (in[e[u][i]] == 0) tmp.push(e[u][i]); // 如果入度为0，将其加入tmp队列
            }
        }
        ans = max(ans, sum); // 更新最大内存消耗
        // 将下一轮的所有入度为0的任务加入队列
        while (!tmp.empty()) {
            q.push(tmp.front());
            tmp.pop();
        }
    }
    cout << ans << endl; // 输出最终的最大内存消耗
    return 0; // 结束程序
}

import java.util.*;

public class Main {
    static final int M = 20;
    static int[] in = new int[M];
    static int[] a = new int[M];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer>[] e = new ArrayList[M];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            e[i] = new ArrayList<>();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int t = scanner.nextInt();
                if (t != 0) {
                    in[i]++; // 拓扑排序入度++
                    e[j].add(i);  // 表示有一条j到i的边
                }
            }
        }

        Queue<Integer> q = new LinkedList<>();
        Queue<Integer> tmp = new LinkedList<>(); // tmp保存本轮产生的所有入度为0的点，q表示已经入度为零的点
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                q.add(i); // 加入初始点
            }
        }

        int ans = 0;
        while (!q.isEmpty()) {
            int sum = 0;
            while (!q.isEmpty()) {
                int u = q.poll();
                sum += a[u];  // 本轮所有点消耗求和
                for (int i = 0; i < e[u].size(); i++) {
                    int v = e[u].get(i);
                    in[v]--;
                    if (in[v] == 0) {
                        tmp.add(v); 
                    }
                }
            }
            ans = Math.max(ans, sum);
            q.addAll(tmp);// 下一轮的点
            tmp.clear();
        }

        System.out.println(ans);
    }
}

from collections import deque

M = 605
in_degree = [0] * M
a = [0] * M
e = [[] for _ in range(M)]

n = int(input())
a[1:n+1] = map(int, input().split())

for i in range(1, n+1):
    row = list(map(int, input().split()))
    for j in range(1, n+1):
        if row[j-1]:
            in_degree[i] += 1 # 拓扑排序入度++
            e[j].append(i) # 表示有一条j到i的边

q = deque()
tmp = deque() # tmp保存本轮产生的所有入度为0的点，q表示已经入度为零的点

for i in range(1, n+1):
    if in_degree[i] == 0:
        q.append(i) # 加入初始点

ans = 0

while q:
    total_sum = 0
    while q:
        u = q.popleft()
        total_sum += a[u]  # 本轮所有点消耗求和
        for v in e[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                tmp.append(v)
    ans = max(ans, total_sum)
    q.extend(tmp) # 下一轮的点
    tmp.clear()

print(ans)