该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

农夫 John 的 N 头(1 <= N <= 50,000) 奶牛(编号 1..N)正计划逃跑去加入马戏团。 它们的蹄子妨碍它们走钢丝或荡秋千（而且它们最后的用加农炮放火的尝试遭受重大失败）。所以，它们不得不决定练习表演杂技。这些奶牛不是很有创造性而且只提出了一个杂技项目：叠罗汉。奶牛正试着算出它们能堆在一起 的顺序。每只奶牛都有一个重量 W_i(1 <= W_i <= 10,000),力气 S_i(1 <= S_i<= 1,000,000,000)。对一只奶牛而言，风险等于在它头上的所有奶牛重量之和（当然不包括它自己的重量）减去它的力气（所以越壮的牛风险越小）。你的任务是决定一个顺序,使得所有奶牛的风险最大值最小。

Format

Input

第一行：一个整数 N.

第 2 到 N+1 行: 第 i+1 行两个分开的整数表示牛 i 的重量 W_i 和力气 S_i。

Output

第一行：一个整数，表示所有奶牛风险最大值的最小值。

Samples

3
10 3
2 5
3 3

2

Limitation

输出说明: : 把重为 10 的奶牛放在底部。它将支撑其余两头牛，所以它的风险是 2+3-3=2。其他两头牛风险比它低。