‹ 上一题 下一题 ›

s09190. 反悔上限 未做

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

题目描述

分装站按固定流程处理 件代派任务:每天恰好完成一件,任务按给定顺序逐个处理,第 件须在时段 或更早完成(保证 ),报酬为 。站里只有 张退货面单,流程如下:

  1. 任务 先直接进入保留集合;
  2. 若保留集合中的任务数超过 :
    • 若手里还有退货面单:用掉一张,退掉集合中报酬最低的任务(报酬相同时退编号最小的),保留新任务;
    • 若面单已用完:放弃新任务(不进入保留集合,也不消耗面单);
  3. 否则无操作。

处理完全部任务后,输出保留集合的报酬总和与实际用掉的退货面单数。

输入格式

第一行两个整数 。

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

输出格式

两行:第一行保留任务的报酬总和;第二行实际用掉的退货面单数。

样例 1

样例

输入
4 1
1 9
2 5
2 6
3 7
输出
22
1

第 件入选后保留数 超过 ,用掉 张面单退掉报酬最低的编号 (报酬 );此后再无超限。保留 ,报酬 ,面单用了 张。

样例 2

面单 张:第 件超限时只能放弃(编号 未入选);第 件照常入选。保留 ,报酬 ,面单用了 张。

数据范围

;;;。

输入
输出

            
答案