题目描述

Every morning, Farmer John's $n \ (1 \leq n \leq 2.5\times 10^4)$ cows all line up for milking. In an effort to streamline the milking process, FJ has designed a two-stage milking process where the line of cows progresses through two barns in sequence, with milking taking part sequentially in both barns. Farmer John milks cows one by one as they go through the first barn, and his trusty sidekick Farmer Rob milks the cows (in the same order) as they are released from the first barn and enter the second barn. Unfortunately, Farmer John's insistence that the cows walk through both barns according to a single ordering leads to some inefficiencies. For example, if Farmer John takes too long to milk a particular cow, Farmer Rob might end up sitting idle with nothing to do for some time. On the other hand, if Farmer John works too fast then we might end up with a long queue of cows waiting to enter the second barn. Please help Farmer John decide on the best possible ordering of cows to use for the milking, so that the last cow finishes milking as early as possible. For each cow $i$ we know the time $a_i$ required for milking in the first barn and the time $b_i$ required for milking in the second barn.
Both $a_i$ and $b_i$ are in the range $1\dots 2\times 10^4$.

每天早晨，约翰的 $n$ 头奶牛都排成一列，逐一挤奶。为了提高挤奶的速率，约翰把整个挤奶过程划分成两道工序，每头牛都得连续地完成这些挤奶工序。奶牛们一个接一个地进入挤奶的牛棚，约翰负责实行第一道工序，第二道工序则让他的好友萝卜帮助完成。并且，如果某头奶牛先于另一头奶牛开始进行第一道工序，那么她开始第二道工序的时间也一定在那一头奶牛之前。约翰发现，如果奶牛们按某种顺序排队进行挤奶，那么可能会在排队等待上多花很多的时间。比方说，如果约翰要花很长时间才能完成某头奶牛挤奶时的第一道工序，那么萝卜可能会有一段时间没有事做。当然，如果约翰的工作完成得太快，萝卜面前就会有很多奶牛排起长队。

请你帮助约翰计算一下，如果按照最优的排队方式，最少需要多少时间才能把所有奶牛都挤过奶。对于每头奶牛，我们都知道在她身上完成第一道工序所需的时间 $a_i$，以及完成第二道工序的时间 $b_i$。

输入格式

• Line $1$: A single integer, $n$.
• Lines $2\dots 1+n$: Line $i+1$ contains two space-separated integers $a_i$ and $b_i$ for cow $i$.

第一行一个整数 $n$。接下来 $n$ 行，每行两个整数表示第 $i$ 头牛的 $a_i,b_i$ 值。

输出格式

• Line $1$: The minimum possible time it takes to milk all the cows, if we order them optimally.

输出按照最优方案排队后，最少需要多少时间才能完成对所有奶牛的挤奶。

3
2 2
7 4
3 5

16

样例说明

把奶牛们按照 $3,1,2$ 的顺序排队，这样挤奶总共花费 $16$ 个单位时间。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 2.5\times 10^4$，$1 \leq a_i,b_i \leq 2\times 10^4$。

题目来源

Gold