问题 1261 --广告问题

1261: 广告问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

“你知不知道,在未来,你将要领导我们去对抗这世界上最庞大的黑暗势力?可是你却在这里贴小广告?一点没有身为领导者的觉悟啊。”李旭琳一副恨铁不成钢的表情。

“哈,像我这么普通的魔法学徒,满大街都是,就算是真的,你也应该早点穿越过来啊,你这么晚才来,能来得及吗?”小墨老师站在魔法世界最繁华的商业街上东张西望。

“一切皆有可能,只要肯努力,任何时候学习都来得及。这是未来的你一直教导我们的。”李旭琳继续坚持。

“好了好了,先贴广告吧,完不成任务,中午广告商不给盒饭吃的。”小墨老师开始埋头工作了。

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

输入

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

输出

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

样例输入

1
5 10
1 10
20 27
0 -3
15 15
8 2
7 30
-1 -10
27 20
2 9
14 21

样例输出

19
-5
-4
-3
-2
-1
0
4
5
6
7
8
15
18
19
20
21
25
26
27

提示

来源

[提交][状态]