P1842 [USACO05NOV] Cows Playing Acrobatics

Farmer John has $N$ cows, numbered $1\sim N$ in order. What FJ does not know is that all his cows dream of escaping the farm to join the circus. They soon discover that their clumsy hooves cannot stand steadily on a tightrope or a swinging trapeze (they even tried loading themselves into a cannon, but the outcome, as you might guess, was tragic). In the end, they decide to practice the simplest acrobatics: stacking all the cows on top of each other. For example, the first cow stands on the second, the second stands on the third, and so on... the $N$-th cow is at the bottom.

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.

The first line contains an integer $N$. The next $N$ lines each contain two integers $W_i$ and $S_i$.

Output a single integer, the minimal overall squashed index.

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