题目背景

原《线段覆盖》请做P1803

题目描述

作为一个富有经营头脑的富翁，小 $L$ 决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数，（我们用 $E_{i,j}$ 表示 $i$ 经理对 $j$ 经理的了解程度），即当经理 $i$ 和经理 $j$ 同时被雇佣时，经理 $i$ 会对经理 $j$ 做出贡献，使得所赚得的利润增加 $E_{i,j}$。

当然，雇佣每一个经理都需要花费一定的金钱 $A_i$，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小 $L$ 当然不会雇佣他。然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少 $E_{i,j}$（注意：这里的 $E_{i,j}$ 与上面的 $E_{i,j}$ 是同一个）。

作为一个效率优先的人，小 $L$ 想雇佣一些人使得净利润最大。你可以帮助小 $L$ 解决这个问题吗？

输入格式

第一行有一个整数，表示经理的个数。

第二行有 $N$ 个整数 $A_i$ 表示雇佣每个经理需要花费的金钱。

接下来的 $N$ 行中一行包含 $N$ 个数，表示 $E_{i,j}$，即经理 $i$ 对经理 $j$ 的了解程度。满足 $E_{i,j}=E_{j,i}$。

输出格式

第一行包含一个整数，即所求出的最大值。

3
3 5 100
0 6 1
6 0 2
1 2 0

1

提示

• $20\%$ 的数据中 $N\le 10$；
• $50\%$ 的数据中 $N\le 100$；
• $100\%$ 的数据中 $N\le 1000$，$E_{i,j}<2^{31}$，$A_i<2^{31}$。

From 林衍凯。