[国家集训队]人员雇佣

题目背景

原《线段覆盖》请做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}$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

1

说明

20%的数据中$N<=10$; 50%的数据中$N<=100$; 100%的数据中$N<=1000$, $E_{i,j} < 2^{31}, A_i< 2^{31}$。 From 林衍凯