Building a Human Tower

You want to build an N-floor tower with N acrobats (1 <= N <= 50,000), placing exactly one acrobat on each floor. An acrobat on a floor must support the total weight of every acrobat above them.

Each acrobat i has a weight Wi (1 <= Wi <= 10,000) and a strength Si (1 <= Si <= 1,000,000,000). In a completed tower, that acrobat's risk is (the total weight of all acrobats above them) - Si. The tower's maximum risk is the largest risk among all acrobats.

All participating acrobats are fixed, but their order can vary. Find the minimum possible value of the tower's maximum risk.

The first line contains N.

Each of the next N lines contains two integers Wi and Si, the weight and strength of one acrobat.

Print the minimum possible maximum risk.