题目描述

一支由 $N$ 名队员组成的探险队需要搭建一列人梯。人梯中每名队员恰好出现一次，需要确定他们从上到下的排列顺序。

第 $i$ 名队员的体重为 $W_i$，强壮度为 $P_i$。一名队员的压力值等于他上方所有队员的体重之和减去他的强壮度。压力值可能为负数。

整列人梯的压力值为所有队员压力值中的最大值。请合理安排队员顺序，使人梯的压力值尽量小，并输出这个最小值。

输入格式

第一行包含一个整数 $N$，表示队员人数。

接下来 $N$ 行，每行包含两个整数 $W_i,P_i$，分别表示一名队员的体重和强壮度。

输出格式

输出一个整数，表示人梯压力值的最小值。

3
20 10
5 8
6 12

1

样例解释

从上到下依次安排体重和强壮度为 $(5,8)$、$(6,12)$、$(20,10)$ 的队员时，各队员的压力值分别为 $-8$、$-7$、$1$，其中最大值为 $1$。

数据范围与提示

• $1 \le N \le 5 \times 10^4$
• $1 \le W_i \le 10^4$
• $1 \le P_i \le 10^9$