Description

Each cow has its own weight and strength. Cow $i$ has weight $W_i$ and strength $S_i$.

When a cow has other cows standing on her, she gets squashed to some extent. We call this her "squashed index." For any cow, her squashed index equals the total weight of all cows stacked above her (not including herself) minus her strength.

After the cows are stacked in some order, their overall squashed index is the squashed index of the most squashed cow.

Your task is to help the cows find an ordering that minimizes the overall squashed index.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain two integers $W_i$ and $S_i$.

Output Format

Output a single integer, the minimal overall squashed index.

3
10 3
2 5
3 3

2

Hint

Constraints: For $100\%$ of the testdata, $1 \le N \le 5\times 10^4$, $1 \le W_i \le 10^4$, $1 \le S_i \le 10^9$.

Translated by ChatGPT 5