当前没有测试数据。

题目描述

有 $n$ 个任务可以执行，每个任务有两个维度的收益：

• 经验值 $a_i$（可能为正或负）。
• 金币值 $b_i$（可能为正或负）。

你需要选择若干个任务（可以全选，也可以不选），使得所有被选中任务的：

• 总经验值 $\ge 0$。
• 总金币值 $\ge 0$。

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

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

输入格式

第一行输入一个整数 $n$。

第二行到第 $n+1$ 行，每行输入两个整数 $a_i$ 与 $b_i$。

输出格式

输出一个整数表示答案。

样例 #1

输入

4
-10 15
10 -5
-2 -2
1 1

输出

12

样例 #2

输入

5
1 3
-2 5
13 -8
2 0
-3 -4

输出

14

样例 #3

输入

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 \le n \le 20$。

对于 $100\%$ 的数据，$1 \le n \le 300$，$-1000 \le a_i, b_i \le 1000$。