#P6243. [USACO06OPEN] The Milk Queue G
[USACO06OPEN] The Milk Queue G
题目背景
题目是经过简写保证不改变原有题意的题目。
题目描述
每早,FJ 的 头奶牛都排成一列挤奶.一个个进到仓库,为提高速率,FJ 把整个挤奶过程划分成两道工序,FJ负责实行第一道,第二道由 Rob 完成。
如果某头牛先于另一头牛开始进行第一道工序,那么她同样先开始第二道工序。
FJ 发现,如果奶牛们按某种顺序排队进行挤奶,那么可能会在排队等待上多花很多的时间。比如,如果 FJ 要花很长时间才能完成某头奶牛的第一道工序,那么 Rob 就会浪费一段时间。反之如果 FJ 的工作完成得太快,Rob 面前会有很多奶牛排起长队。
请你计算按最优方式排队后最少需要多少时间才能挤完奶。对于每头奶牛,数据提供第一道工序的时间 和第二道工序的时间 。
输入格式
第一行一个整数 。
接下来 行,每行两个整数表示第 头牛的 , 值。
输出格式
输出按最优方案排队后挤奶所需的最短时间。
3
2 2
7 4
3 5
16
提示
样例说明
把奶牛们按照 3,1,2 的顺序排队,这样挤奶总共花费 16 个单位时间.