挤奶调度(Milk Scheduling S)

题目描述

FJ 有 $N$（$1 \le N \le 10,000$）头牛要挤牛奶，为每头牛挤牛奶需要花费 $1$ 单位时间。

奶牛很厌烦等待，奶牛 $i$ 在它的截止时间 $d_i$（$1 \le d_i \le 10,000$）前能挤出 $g_i$（$1 \le g_i \le 1000$）加仑的牛奶，否则将不能挤出牛奶。时间 $t$ 开始时为 $0$，即在时间 $t=x$ 之前，最多可以给 $x$ 头奶牛挤牛奶。

请计算 FJ 的最大挤奶量。

输入格式

第一行一个整数 $N$。

第 $2$ 至第 $(N+1)$ 行，第 $(i+1)$ 行两个整数 $g_i$ 和 $d_i$。

输出格式

一行一个整数，表示 FJ 最多能得到多少加仑的牛奶。

样例输入 #1

4
10 3
7 5
8 1
2 1

样例输出 #1

25

数据范围

有 $4$ 头奶牛。第一头奶牛如果在时刻 $3$ 之前（不包含时刻 $3$）被挤可以产出 $10$ 加仑牛奶，其它奶牛以此类推。

FJ 在 $0$ 时刻开始给奶牛 $3$ 挤牛奶（放弃在奶牛 $4$ 的时间限制之前给它挤牛奶，因为和奶牛 $3$ 冲突），消耗 $1$ 单位时间并得到 $8$ 加仑的牛奶；在时刻 $1$ 给奶牛 $1$ 挤牛奶，在时刻 $2$ 给奶牛 $2$ 挤牛奶。

一共获得 $8+10+7=25$ 加仑的牛奶。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接