bzoj#P2039. [2009国家集训队]employ人员雇佣
[2009国家集训队]employ人员雇佣
题目描述
作为一个富有经营头脑的富翁,小 L 决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,(我们用 表示 经理对 经理的了解程度),即当经理 和经理 同时被雇佣时,经理 会对经理 做出贡献,使得所赚得的利润增加 。当然,雇佣每一个经理都需要花费一定的金钱 ,对于一些经理可能他做出的贡献不值得他的花费,那么作为一个聪明的人,小 L 当然不会雇佣他。然而,那些没有被雇佣的人会被竞争对手所雇佣,这个时候那些人会对你雇佣的经理的工作造成影响,使得所赚得的利润减少 (注意:这里的 与上面的 是同一个)。作为一个效率优先的人,小 L 想雇佣一些人使得净利润最大。你可以帮助小 L 解决这个问题吗?
输入格式
第一行有一个整数 表示经理的个数。
第二行有 个整数 表示雇佣每个经理需要花费的金钱。
接下来的 行中一行包含 个数,表示 ,即经理 对经理 的了解程度。
输出格式
第一行包含一个整数,即所求出的最大值。
样例输入
3
3 5 100
0 6 1
6 0 2
1 2 0
样例输出
1
数据规模与约定
对于 的数据,。
对于 的数据,。
对于 的数据,,,,。
题目来源
版权所有者:林衍凯