题目描述

有n头奶牛，每头奶牛有两个属性：重量w和强壮度s。现在这些奶牛要玩一个叠罗汉的游戏，即一头奶牛要站在另一头奶牛的背上。最后只有一头奶牛站在地面上，从上到下刚好有n层。这时候，奶牛的难受值为它背上的奶牛重量之和减去它自己的强壮度。难受值的最小值为0. 请问，要如何安排奶牛叠罗汉的顺序，才能使最难受的奶牛的难受值最小。

输入格式

第一行，一个正整数，表示n。 接下来有n行，每行两个整数，分别表示一头奶牛的重量和强壮度。

输出格式

一个整数，表示最难受的奶牛的最小难受值。

样例

5
4 3
2 5
1 9
4 8
10 10

1

数据范围与提示

$ n\leq 5*10^4,1 \leq s \leq 10^4,1 \leq w \leq 10^9 $