‹ 上一题 下一题 ›

s09150. 柜台的最大收益 未做

1000 ms 256 MB 测试点 10 通过率 33% S-06·贪心进阶与反悔贪心优先队列贪心

题目描述

快餐柜台有一个服务窗口,从时刻 开始,每分钟恰好处理一份订单,一份订单占用整整一分钟。共有 位顾客预约,顾客 的订单必须在时刻 或之前完成,完成后柜台获得收益 ;若拒绝则收益为 。

柜台可以拒绝任意订单,也可以自行决定接受订单的处理顺序(每一分钟至多处理一份)。求能获得的最大总收益。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 。

输出格式

一行一个整数:最大总收益。

样例 1

样例

输入
4
1 4
2 6
2 7
4 5
输出
18

放弃收益 的那份(它占用最紧的时刻 ),接受其余三份,按 处理,得 。

样例 2

五份订单都要求时刻 完成,时刻 只能处理一份,选收益最大的 。

数据范围

;;。答案可能超过 位整数范围。

输入
输出

            
答案