[国家集训队] 人员雇佣

题目背景

原《线段覆盖》请做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\le 10$; - $50\%$ 的数据中 $N\le 100$; - $100\%$ 的数据中 $N\le 1000$,$E_{i,j}<2^{31}$,$A_i<2^{31}$。 From 林衍凯。