4011 - 双重指标

题目描述

n 个任务可以执行,每个任务有两个维度的收益:

  1. 经验值 a_i(可能为正或负)。

  2. 金币值 b_i(可能为正或负)。

你需要选择若干个任务(可以全选,也可以不选),使得所有被选中任务的:

  1. 总经验值 \ge 0

  2. 总金币值 \ge 0

满足以上两个条件的前提下,最大化 总经验值 + 总金币值。

请编程计算出:满足条件的前提下,最大的总经验值+总金币值。

输入

第一行输入一个整数 n

第二行到第 n+1行,每行输入两个整数 a_ib_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 解释

最优方案完成第 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

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 入门


上一题 下一题