题目描述
如果有两个人想平分一堆物品，有一个比较公平的方法是：第一个人首先将这些物品分成两堆，接下来第二个人从这两堆物品中挑走一堆他认为价值较大的物品。若两人对每件物品的估值都是一致的，显然这样做是非常公平的。但问题在于，如果两个人对物品的估值不一致时，知道物品实际价值的人会具有更大的优势。
小爱和小艾正在“公平地”分割 $n$ 件物品。小爱知道每件物品的**价值**与**价格**，而小艾只知道每件物品的**价格**。他们约定，首先由小爱负责将这些物品分成两堆，然后小艾有权先挑走一堆，剩下的另一堆就是留个小爱的。
由于小艾只知道每件物品的**价格**，所以他一定会挑走**价格**之和较大的一堆，若两堆物品的**价格**之和一样大，他会大方地让小爱做选择。
小爱既知道每件物品的**价值**，也知道每件物品的**价格**，所以她可以在分割物品的时候，故意制造一个局面，使得留下的那堆物品的**价值**之和最大，请问她应该如何分割这些物品呢？
输入
第一行：单个正整数 $n$。
第二行到第 $n+1$ 行：每行两个正整数 $a_i$ 和 $b_i$，$a_i$ 表示第 $i$ 件物品的**价值**，$b_i$ 表示第 $i$ 件物品的**价格**。
输出
单个正整数：表示小爱可以得到的物品的最大**价值**之和。
样例输入输出
输入#1
复制
3
10 20
20 40
40 30
提示
+ 对于 $40\%$ 的分数，$1\leq n\leq 20$；
+ 对于 $70\%$ 的分数，$1\leq n\leq 50$，$1\leq a_i,b_i\leq 500$；
+ 对于 $100%$ 的分数，$1\leq n\leq 100$，$1\leq a_i,b_i\leq 10000$。
样例1说明:小爱将前两件物品分在一堆，将最后一件分在另一堆，小艾会挑走前一堆（因为有价格更高），小爱将得到最后一件物品，其价值为40