#P1791. [国家集训队] 人员雇佣

[国家集训队] 人员雇佣

题目背景

原《线段覆盖》请做P1803

题目描述

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

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

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

输入格式

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

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

接下来的 NN 行中一行包含 NN 个数,表示 Ei,jE_{i,j},即经理 ii 对经理 jj 的了解程度。满足 Ei,j=Ej,iE_{i,j}=E_{j,i}

输出格式

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

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

提示

  • 20%20\% 的数据中 N10N\le 10
  • 50%50\% 的数据中 N100N\le 100
  • 100%100\% 的数据中 N1000N\le 1000Ei,j<231E_{i,j}<2^{31}Ai<231A_i<2^{31}

From 林衍凯。