UOJ Logo LFYZ Online Judge

LFYZOJ

#63. 超市

统计

问题描述

穰子开了一家超市,有 $n$ 个货物。每个货物都有一个价值 $p$ 和一个限制 $d$。也就是说,这个货物只能在时间 $1 \sim d$ 之间出售。并且,一个时间只能出售一个货物。

请你告诉穰子她能获得的最大价值。

输入格式

第一行一个整数 $n$。

下来 $n$ 行每行两个整数 $p,d$。

输出格式

一个整数,是你的答案。

样例一

input

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

output

185

数据范围与约定

对于 $100\%$ 的数据,$1 \leq n,p,d \leq 10^5$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$

来源

poj 1456