Le $N$ mucche di Farmer John ($1 \le N \le 50{,}000$), numerate $1..N$, vogliono scappare al circo. Gli zoccoli impediscono funambolismo e trapezio (e l’ultimo tentativo di sparare una mucca da un cannone è fallito miseramente). Decidono di praticare acrobazie.

Non sono molto creative e hanno ideato un solo numero: stare una sopra l’altra in una pila verticale di una certa altezza. Cercano l’ordine nella pila.

Ogni mucca ha peso ($1 \le W_i \le 10{,}000$) e forza ($1 \le S_i \le 1{,}000{,}000{,}000$). Il rischio di crollare è il peso totale delle mucche sopra (escluso il proprio) meno la forza, quindi una mucca più forte ha meno rischio. Trovate l’ordine che minimizza il rischio massimo di tutte.

Input

• Riga 1: un intero $N$.
• Righe $2..N+1$: la riga $i+1$ descrive la mucca $i$ con due interi separati da uno spazio, $W_i$ e $S_i$.

Output

• Riga 1: un intero, il rischio massimo di tutte le mucche in qualsiasi ordine ottimale che minimizzi il rischio.

Esempi

Input 1

3
10 3
2 5
3 3

Output 1

2

Nota

Mettete in basso la mucca di peso 10. Sostiene le altre due, quindi il suo rischio è $2+3-3=2$. Le altre hanno rischio inferiore.