Description

丁丁的房间里有n块不同的积木，每块积木都有自己的重量与强度。小明想要利用他们叠成一座高高的木塔，也就是一个个叠上去。 这样每块积木都会有一个压力，我们这样定义它的压力：叠在它上面的积木的总重量减去它自身的强度。 现要你决定一个叠放次序，使得压力值最大的那块积木的压力值最小。

Input

输入包含多组测试数据。 每组测试数据的第一行包含一个整数n，表示积木的块数。 接下来有n行，每行有两个整数w、s，分别表示积木的重量与强度（ 1<=n<=50000,1<=w<=10000,1<=s<=1000000000）。

Output

针对每组测试数据，输出压力值最大的那块积木的压力值。

Sample

Input

3
10 3
2 5
3 3
1
2 2

Output

2
-2

Hint

输入比较大，建议使用scanf！