5736 - 大神排队

现在共有n个同学要排成一列,每个同学有两个属性:影响力和承受能力。给一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受力。

请安排一下排队顺序,尽量使受到心理创伤最大的同学少受创伤。

输入

第1行是整数n,表示同学人数。

第2~n+1行,每行两个自然数,分别是该同学的影响力和承受能力。

输出

输出1行1个整数,为你安排的顺序中受到心理创伤最大的同学受到的创伤。

样例

输入

3
10 3
2 5
3 3

输出

2

提示

【数据规模】

对于100%的数据满足:1≤n≤50000,1≤影响力≤10000,1≤承受能力≤10^9

来源

课课通

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题