Sobytiynyy Proyekt Casino is located in San Petersburg, one of the most beautiful cities in Russia, known (besides being where ITMO is located) by its delightful Hermitage Museum. The casino's owner, a former ICPC contestant who never made it to the world finals, is creating a new game (as the traditional games are not appreciated there...) and he wants revenge on his fellow competitors, by punishing players who are trying to play his game optimally.
In each round, the players get a pair of integers $(p, f)$, where $p > 0$. The player gets (p) rubles and he or she may decide to leave the game by paying (f) rubles (or receiving (-f) rubles, if (f) is negative). Depending on how they play, players may end the game while owing money...
Note also that if the player reaches the last pair, he is forced to pay (f_N).
Help the casino's owner by finding an ordering of the (N) pairs which minimize the gains from a player who plays optimally. Your code must print how much the player would earn if she played in the ordering of pairs that minimizes her gain.
You should read the number (N) of pairs in the first line of input.
After this (N) lines will follow, each with two numbers separated by a space, $p$ and $f$.
*Constraints*
Print a single integer: how much an optimal player would gain in an ordering of pairs that minimizes her gain.
Let us analyze the possible permutations of the sequence of pairs for the first case:
Both permutations $(1, 2), (3, 3), (2, 1)$ and $(3, 3), (1, 2), (2, 1)$ award 5 to an optimal player. The permutations $(2, 1), (3, 3), (1, 2)$ and $(3, 3), (2, 1), (1, 2)$ award at most 4.
Finally, the permutations $(1, 2), (2, 1), (3, 3)$ and $(2, 1), (1, 2), (3, 3)$ award at most 3 to a player. Thus, 3 is the smallest value that an optimal player can get in this game.
## Input
You should read the number (N) of pairs in the first line of input.After this (N) lines will follow, each with two numbers separated by a space, $p$ and $f$.*Constraints* $1 <= N <= 10^5$ $0 <= p_i <= 10^9$ for all $i$ $-10^9 <= f_i <= 10^9$ for all $i$
## Output
Print a single integer: how much an optimal player would gain in an ordering of pairs that minimizes her gain.
[samples]
## Note
Let us analyze the possible permutations of the sequence of pairs for the first case:Both permutations $(1, 2), (3, 3), (2, 1)$ and $(3, 3), (1, 2), (2, 1)$ award 5 to an optimal player. The permutations $(2, 1), (3, 3), (1, 2)$ and $(3, 3), (2, 1), (1, 2)$ award at most 4.Finally, the permutations $(1, 2), (2, 1), (3, 3)$ and $(2, 1), (1, 2), (3, 3)$ award at most 3 to a player. Thus, 3 is the smallest value that an optimal player can get in this game.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of pairs.
Let $ P = \{(p_i, f_i) \mid i \in \{1, \dots, N\}\} $ be the set of pairs, where $ p_i > 0 $, $ f_i \in \mathbb{Z} $.
**Constraints**
- $ 1 \leq N \leq 10^5 $
- $ p_i > 0 $, $ f_i \in \mathbb{Z} $ for all $ i \in \{1, \dots, N\} $
**Objective**
Find a permutation $ \sigma \in S_N $ of the indices $ \{1, \dots, N\} $ that minimizes the maximum cumulative gain an optimal player can achieve under the following rules:
- The player starts with 0 rubles.
- At step $ j \in \{1, \dots, N\} $, the player receives $ p_{\sigma(j)} $ rubles, then may choose to stop and pay $ f_{\sigma(j)} $ rubles (i.e., gain $ p_{\sigma(j)} - f_{\sigma(j)} $), or continue.
- If the player reaches the last pair ($ j = N $), they are forced to pay $ f_{\sigma(N)} $.
The player plays optimally to **maximize** their final gain.
We seek the **minimum possible** such maximum gain over all permutations $ \sigma $:
$$
\min_{\sigma \in S_N} \left( \max_{1 \leq k \leq N} \left( \sum_{j=1}^{k} p_{\sigma(j)} - f_{\sigma(k)} \right) \right)
$$