公平分割(Fair Division)

题目背景

如果有两个人想平分一堆物品，有一个比较公平的方法是：首先有一个人将这些物品分成两堆，接下另一个人从这两堆物品中挑走一堆他认为价值较大的物品。若两人对每件物品的估值都是一致的，显然这样做是非常公平的。但问题在于，如果两个人对物品的估值不一致时，知道物品实际价值的人会具有更大的优势。

题目描述

小爱和小艾正在协商分割 n 件物品。小爱知道每件物品的价值与价格，而小艾只知道每件物品的价格。他们约定，首先由小爱负责将这些物品分成两堆，然后小艾挑选拿走一堆，剩下的就是小爱的。

由于小艾只知道每件物品的价格，所以他一定会挑走价格之和较大的一堆，若两堆物品的价格之和一样大，他会客气地让小爱做出选择。

小爱既知道每件物品的价值，也知道每件物品的价格，所以她可以在分割物品的时候，故意制造一个局面，使得小艾拿走价格大但价值低的一堆物品，请计算并输出小爱可以留下的物品的最大价值之和。

输入格式

第一行：单个整数 n。 第二行到第 n+1 行：每行两个整数 aᵢ 和 bᵢ，aᵢ 表示第 i 件物品的价值，bᵢ 表示第 i 件物品的价格。

输出格式

单个整数：表示小爱可以得到的物品的最大价值之和。

数据范围

• 对于 40% 的分数，1 ≤ n ≤ 20；
• 对于 70% 的分数，1 ≤ n ≤ 50，1 ≤ aᵢ,bᵢ ≤ 500；
• 对于 100% 的分数，1 ≤ n ≤ 100，1 ≤ aᵢ,bᵢ ≤ 10000。

样例输入 #1

3
10 20
20 40
40 30

样例输出 #1

40

样例1说明：小爱将前两件物品分在一堆，将最后一件分在另一堆，小艾会挑走前一堆（因为有价格更高），小爱将得到最后一件物品，其价值为40。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布