题目描述
退货台上依次到来 个任务,输入顺序即到来顺序,任务编号 到 。每个任务的加工时长均为 分钟,任务 的截止时刻为 ,完成后获得报酬 。同一时刻只能加工一个任务,机器从时刻 开始,加工不可中断。
对这批任务执行如下固定流程:先把所有任务按截止时刻升序排列,截止时刻相同的按到来编号升序排列;然后依次逐个处理,每个任务先直接加入保留集合(集合大小加一,报酬累加);若保留集合的大小超过当前任务的截止时刻,则退掉保留集合中报酬最低的一个任务并扣回它的报酬,记一次退货;若报酬最低的任务有多个,退其中到来编号最小的一个。被退掉的任务彻底消失。
求流程结束后保留任务的总报酬,以及全部被退任务的到来编号之和。(可以证明,该总报酬就是合法加工方案总报酬的最大值。)
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 。
输出格式
两行,每行一个整数:第一行是保留任务的总报酬,第二行是被退任务到来编号之和。
样例 1
样例
输入
4 2 5 2 5 3 9 3 7
输出
21 1
按截止时刻排序后依次处理:前两个任务入集合后大小 ;第三个入集合后大小 ,报酬最低的是前两个任务(同为 ),退到来编号最小的任务 ,大小回到 ;第四个入集合后大小 。保留任务 ,总报酬 ,被退编号之和 。
样例 2
输入
4 1 4 1 9 2 6 2 3
输出
15 5
任务 入集合后大小 ;任务 入集合后大小 ,退报酬最低的任务 (报酬 );任务 入集合后大小 ;任务 入集合后大小 ,退报酬最低的任务 (报酬 )。保留任务 ,总报酬 ,被退编号之和 。
数据范围
;;。总报酬与编号之和可能超过 位整数范围。