‹ 上一题 下一题 ›

s09191. 同酬退货台 未做

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

题目描述

退货台上依次到来 个任务,输入顺序即到来顺序,任务编号 到 。每个任务的加工时长均为 分钟,任务 的截止时刻为 ,完成后获得报酬 。同一时刻只能加工一个任务,机器从时刻 开始,加工不可中断。

对这批任务执行如下固定流程:先把所有任务按截止时刻升序排列,截止时刻相同的按到来编号升序排列;然后依次逐个处理,每个任务先直接加入保留集合(集合大小加一,报酬累加);若保留集合的大小超过当前任务的截止时刻,则退掉保留集合中报酬最低的一个任务并扣回它的报酬,记一次退货;若报酬最低的任务有多个,退其中到来编号最小的一个。被退掉的任务彻底消失。

求流程结束后保留任务的总报酬,以及全部被退任务的到来编号之和。(可以证明,该总报酬就是合法加工方案总报酬的最大值。)

输入格式

第一行一个整数 。

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

输出格式

两行,每行一个整数:第一行是保留任务的总报酬,第二行是被退任务到来编号之和。

样例 1

样例

输入
4
2 5
2 5
3 9
3 7
输出
21
1

按截止时刻排序后依次处理:前两个任务入集合后大小 ;第三个入集合后大小 ,报酬最低的是前两个任务(同为 ),退到来编号最小的任务 ,大小回到 ;第四个入集合后大小 。保留任务 ,总报酬 ,被退编号之和 。

样例 2

任务 入集合后大小 ;任务 入集合后大小 ,退报酬最低的任务 (报酬 );任务 入集合后大小 ;任务 入集合后大小 ,退报酬最低的任务 (报酬 )。保留任务 ,总报酬 ,被退编号之和 。

数据范围

;;。总报酬与编号之和可能超过 位整数范围。

输入
输出

            
答案