#J3034. 卖东西

卖东西

题目描述

大白是小店管理员,他在想如何提升自己店的销售利润,一天小Q把店铺里的商品以及过期时间告诉了大白。你能帮助大白合理安排每天的商品销售吗?每天只能售卖一件物品哦!

说明: 每一件物品都有wi以及过期时间di,每天只能卖一件物品,并且过期的物品不能再卖掉了。如何安排每天卖掉的物品使得小店的利润收益最大?

输入格式

输入包含多组测试用例

每组测试用例,以输入整数n开始,接下来输入n对wi和di,分别代表第i件物品卖出的利润和过期时间。

在输入中,数据间可以隔着多个空格,输入一直到文件的最终结尾时终止输入,要求保证数据的正确性。

输出格式

输出格式:

要求包含每组物品的一个最大收益值。 每个结果占一行。


数据范围说明:

0≤n≤100000,
1≤wi,di≤10000.
4  50 2  10 1   20 2   30 1

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

80
185
</p>