题目描述

有 $n$ 名同学排成一列。每名同学有影响力 $w_i$ 和承受能力 $s_i$，心理创伤指数等于排在他前面的同学影响力之和减去 $s_i$。请安排顺序，使所有同学中最大的心理创伤指数尽可能小。指数可以为负数。

输入格式

第一行整数 $n$。接下来 $n$ 行，每行两个整数 $w_i,s_i$。

输出格式

输出最大创伤指数的最小可能值。

样例

3
10 3
2 5
3 3

2

数据范围

$1\le n\le50000$，$1\le w_i\le10000$，$1\le s_i\le10^9$。