题目描述

作为一个富有经营头脑的富翁，小 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$ 表示经理的个数。
第二行有 $N$ 个整数 $A_i$ 表示雇佣每个经理需要花费的金钱。
接下来的 $N$ 行中一行包含 $N$ 个数，表示 $E_{i,j}$，即经理 $i$ 对经理 $j$ 的了解程度。

输出格式

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

样例输入

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

样例输出

1

数据规模与约定

对于 $20\%$ 的数据，$N \leq 10$。
对于 $50\%$ 的数据，$N \leq 100$。
对于 $100\%$ 的数据，$N \leq 10^3$，$E_{i,j} \leq 2^{31}-1$，$A_i \leq 2^{31}-1$，$E_{i,j}=E_{j,i}$。

题目来源

版权所有者：林衍凯