You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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 最多能得到多少加仑的牛奶。

4 
10 3 
7 5 
8 1 
2 1 

25 

说明/提示

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

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

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