题目描述
货运站收到 笔发运订单。发运口按时段发货:时段 ,每个时段恰好发运一笔订单。第 笔订单若在时段 或更早发运,站里赚到利润 ;放弃则不赚。
调度员的排单流程固定如下:
- 把订单按截止时段升序排列,截止相同的按输入编号升序;
- 逐笔入选:订单先进入保留集合;若保留集合中的订单数超过当前订单的截止时段,退掉集合中利润最低的一笔(利润相同时退编号最小的);
- 流程结束后,保留集合即最终发运方案。
输出最终发运方案的总利润与发运订单数。其中总利润等于所有不超期方案中利润总和的最大值。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 。
输出格式
两行:第一行总利润;第二行发运订单数。
样例 1
样例
输入
4 1 3 1 6 2 8 3 5
输出
19 3
按流程处理顺序为 :入选编号 (截止 )时保留数 超过 ,退掉利润最低的编号 (利润 );此后无超限。最终保留 ,利润 ,发运 笔。
样例 2
输入
5 2 7 2 7 2 9 2 4 1 8
输出
17 2
排序后处理顺序为 :入选编号 时退编号 (利润并列 ,编号小的先退);入选编号 时退编号 ;入选编号 时刚入选的编号 (利润 )自己被退。最终保留 ,利润 ,发运 笔。
数据范围
;;。总利润可能超过 位整数范围。