题目背景

原《线段覆盖》请做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<=10$；
50%的数据中$N<=100$；
100%的数据中$N<=1000$， $E_{i,j} < 2^{31}, A_i< 2^{31}$。

From 林衍凯