#10462. 多任务选择

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

小途手上有n个任务,第i个任务的起止时刻分别为( a_i, b_i )。小涂任何时刻只能进行一个任务,只有在当前任务完成之后才能进行下一个任务。

请帮助小涂进行任务合理选择,使得从0时刻开始,到m时刻结束,他能够完成做多的任务,并输出该任务序列和完成的任务数

输入格式

输入任务数n和结束时刻m

依次输入每个任务的起止时刻

输出格式

按照结束时刻升序输出任务序列, 输出完成任务总数

样例

样例输入

5 8
1 2
1 4
2 4
3 5
4 8

样例输出

1 2
2 4
4 8
3

数据范围与提示

1<=n<= 10^4 , m<= 10^5 , 0<= a_i < b_i <=m