Minimize the Maximum Flattening Index

In this problem, there are n cows. The i^th cow has a weight \(W_i\) and a strength \(S_i\). When cows are stacked on top of one another, each cow gets compressed. The flattening index of cow \(i\) is defined as

[ F_i = \left(\sum_{\text{cows above } i} W_j\right) - S_i. ]

After the cows are stacked in some order, the total flattening index of the stack is defined as the maximum flattening index among all cows (i.e. the cow that is compressed the most):

[ F = \max_{i} ;\bigl{F_i\bigr}. ]

Your task is to find an ordering of the cows such that the total flattening index \(F\) is minimized.

inputFormat

The first line contains a single integer \(n\) (1 \(\leq n \leq\) some limit), the number of cows. Each of the next \(n\) lines contains two space-separated integers \(W_i\) and \(S_i\), representing the weight and strength of the \(i^th\) cow.

outputFormat

Output a single integer, the minimum possible total flattening index that can be achieved by stacking the cows in an optimal order.

sample

3
10 3
8 5
5 7

10