A2214. 牛奶调度
编程题
普及/提高-
知识点
题目描述
FJ有N(1 <= N <= 10,000)头牛要挤牛奶，每头牛需要花费1单位时间。
奶牛很厌烦等待，奶牛i在它的截止时间d\_i (1 <= d\_i <= 10,000)前挤g(1 <= g\_i <= 1000)的奶，否则将不能挤奶。时间t开始时为0，即在时间t=x时，最多可以挤x头奶牛。
请计算FJ的最大挤奶量。
奶牛很厌烦等待，奶牛i在它的截止时间d\_i (1 <= d\_i <= 10,000)前挤g(1 <= g\_i <= 1000)的奶，否则将不能挤奶。时间t开始时为0，即在时间t=x时，最多可以挤x头奶牛。
请计算FJ的最大挤奶量。
输入格式
* 第 1 行：N 的值。
* 第 2..1+N 行：第 i+1 行包含整数 g_i 和 d_i。
* 第 2..1+N 行：第 i+1 行包含整数 g_i 和 d_i。
输出格式
* 第 1 行：Farmer John 可以获得的最大加仑牛奶数。
输入输出样例
输入 #1
4 10 3 7 5 8 1 2 1
输出 #1
25
说明/提示
有4头奶牛。如果在时间 10 之前挤奶，第一个会产生 3 加仑的牛奶，依此类推。
农场主约翰首先给 3 号奶牛挤奶，放弃了 4 号奶牛，因为与 3 号奶牛发生冲突，她无法在截止日期前挤奶。然后，农场主约翰给 1 号和 2 号奶牛挤奶。
农场主约翰首先给 3 号奶牛挤奶，放弃了 4 号奶牛，因为与 3 号奶牛发生冲突，她无法在截止日期前挤奶。然后，农场主约翰给 1 号和 2 号奶牛挤奶。