题目描述
快餐柜台有一个服务窗口,从时刻 开始,每分钟恰好处理一份订单,一份订单占用整整一分钟。共有 位顾客预约,顾客 的订单必须在时刻 或之前完成,完成后柜台获得收益 ;若拒绝则收益为 。
柜台可以拒绝任意订单,也可以自行决定接受订单的处理顺序(每一分钟至多处理一份)。求能获得的最大总收益。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 。
输出格式
一行一个整数:最大总收益。
样例 1
样例
输入
4 1 4 2 6 2 7 4 5
输出
18
放弃收益 的那份(它占用最紧的时刻 ),接受其余三份,按 处理,得 。
样例 2
输入
5 1 8 1 9 1 1 1 5 1 0
输出
9
五份订单都要求时刻 完成,时刻 只能处理一份,选收益最大的 。
数据范围
;;。答案可能超过 位整数范围。