#P2184. Cow Exhibition
Cow Exhibition
题目描述
“肥胖温顺,又大又笨,它们看起来好傻,一点都不好玩……” —— 达纳・莱昂斯《带枪的奶牛》
奶牛们想向公众证明它们既聪明又有趣。为此,贝西组织了一场奶牛展览。她对 N(1 ≤ N ≤ 100)头奶牛分别进行了全面采访,并为每头奶牛确定了两个值:奶牛的聪明度 Si(-1000 ≤ Si ≤ 1000)和趣味度 Fi(-1000 ≤ Fi ≤ 1000)。
贝西需要选择带哪些奶牛参加展览。她认为,群体的总聪明度 TS 是所有选中奶牛 Si 的总和,总趣味度 TF 是所有选中奶牛 Fi 的总和。贝西希望最大化 TS 与 TF 的和,但同时要求这两个值均非负(因为她必须展示奶牛的全面性;负的 TS 或 TF 会破坏这一点)。请帮助贝西在确保 TS 和 TF 均非负的前提下,最大化 TS + TF 的值。若没有任何奶牛子集能满足 TS 和 TF 均非负,输出 0。
输入
第 1 行:单个整数 N,表示奶牛数量 第 2..N+1 行:每行两个空格分隔的整数 Si 和 Fi,分别表示每头奶牛的聪明度和趣味度
输出
第 1 行:一个整数,即满足 TS ≥ 0 且 TF ≥ 0 的 TS + TF 的最大值。若不存在这样的子集,输出 0。
输入数据 1
5
-5 7
8 -6
6 -3
2 1
-8 -5
输出数据 1
8
提示
输出细节:
贝西选择奶牛 1、3、4,此时 TS = -5+6+2 = 3,TF = 7-3+1 = 5,因此 3+5 = 8。注意,若加入奶牛 2,TS+TF 会提升至 10,但新的 TF 值为负,因此不允许。