#P6243. [USACO06OPEN] The Milk Queue G

[USACO06OPEN] The Milk Queue G

题目背景

题目是经过简写保证不改变原有题意的题目。

题目描述

每早,FJ 的 NN 头奶牛都排成一列挤奶.一个个进到仓库,为提高速率,FJ 把整个挤奶过程划分成两道工序,FJ负责实行第一道,第二道由 Rob 完成。

如果某头牛先于另一头牛开始进行第一道工序,那么她同样先开始第二道工序。

FJ 发现,如果奶牛们按某种顺序排队进行挤奶,那么可能会在排队等待上多花很多的时间。比如,如果 FJ 要花很长时间才能完成某头奶牛的第一道工序,那么 Rob 就会浪费一段时间。反之如果 FJ 的工作完成得太快,Rob 面前会有很多奶牛排起长队。

请你计算按最优方式排队后最少需要多少时间才能挤完奶。对于每头奶牛,数据提供第一道工序的时间 AiA_i 和第二道工序的时间 BiB_i

输入格式

第一行一个整数 NN

接下来 NN 行,每行两个整数表示第 ii 头牛的 AiA_iBiB_i 值。

输出格式

输出按最优方案排队后挤奶所需的最短时间。

3
2 2
7 4
3 5
16

提示

样例说明

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

1N250001\le N\le 25000

1Ai,Bi2×1041\le A_i,B_i\le 2\times 10^4