有 n 个任务可以执行,每个任务有两个维度的收益:
经验值 a_i(可能为正或负)。
金币值 b_i(可能为正或负)。
你需要选择若干个任务(可以全选,也可以不选),使得所有被选中任务的:
总经验值 \ge 0。
总金币值 \ge 0。
在满足以上两个条件的前提下,最大化 总经验值 + 总金币值。
请编程计算出:满足条件的前提下,最大的总经验值+总金币值。
第一行输入一个整数 n。
第二行到第 n+1行,每行输入两个整数 a_i 与 b_i。
输出一个整数表示答案.
4 -10 15 10 -5 -2 -2 1 1
12
5 1 3 -2 5 13 -8 2 0 -3 -4
14
9 38 -38 -38 38 -88 88 -8 8 -3 3 19 5 71 1 7 -927 -827 827
96
最优方案完成第 1 2 4 个任务,既保证了总经验值和总金币值大于 0,且两者总和 -10+15+10-5+1+1 = 12 最大。
对于 40\% 的数据,1 \leq n \leq 20。
对于 100\% 的数据,1 \leq n \leq 300, -1000 \leq a_i,b_i \leq 1000。