2030: 宝典2第七章广告问题

【题目描述】广告问题（ad.cpp/c/pas）uva10148　 Advertisement

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

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

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

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

已知广告商要求小墨老师调查了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