F. 挤奶队列

题目描述

每天早晨，农夫约翰（Farmer John）的 $N$ $(1 \leq N \leq 25000)$ 头奶牛要排队挤奶，挤奶过程分为两道工序，约翰负责第一道工序，他的助手农夫罗布（Farmer Rob）负责第二道工序，且奶牛按同一顺序依次经过两个牛棚完成工序。

对于每头奶牛 $i$ ，已知其在第一道工序所需时间 $A_i$ 和在第二道工序所需时间 $B_i$。

$1 \leq A_i, B_i \leq 20000$

任务：确定奶牛的最佳排队顺序，使得最后一头奶牛完成挤奶的时间尽可能早，求此最少时间

输入格式

• 第 $1$行 ：一个整数 $N$。
• 第 $2$ 行到 $N+1$ 行：每行两个空格分隔的整数 $A_i$ 和$B_i$ ，分别表示第 $i$ 头牛在第一道工序和第二道工序所需的时间。

输出格式

输出一行，一个整数，表示按照最优方案排队后，完成所有奶牛挤奶的最少时间

样例

3
2 2
7 4
3 5

16

样例解释