问题 3734 --广告

3734: 广告

题目描述

  已知广告商要求小墨老师调查了n 位顾客,这n位顾客每天都有固定的活动区间,每段区间至少要帐号k个广告,广告商要求小墨老师在这些区间贴广告,问如何贴广告使其数量最少。

输入

第一行为一个整数,表示测试数据的组数。每组数据的第一行为k和n(1<=k,n<=1000)。随后n行为区间的左右端点。

输出

第一行为一个整数m,表示最少广告数,随后m行为广告的位置。

样例输入输出

输入#1 复制
1
5 10
1 10
20 27
0 -3
15 15
8 2
7 30
-1 -10
27 20
2 9
14 21
输出#1 复制
19
-5
-4
-3
-2
-1
0
4
5
6
7
8
15
18
19
20
21
25
26
27

提示

序号 标题 作者 发表时间 费用 订购数 操作