题目描述

UVA 10148

广告商调查了$\red{n（1≤n≤1 000）}$位顾客，这$\red{n}$位顾客每天都有固定的活动区间，每段区间至少要贴$\red{k（1≤k≤1 000）}$个广告，若区间不够放$\red{k}$个广告，则该区间全部填满，广告商要在这些区间贴广告，问如何贴广告使其数量最少。

输入格式

第一行为一个整数，表示测试数据的组数。每组数据的第一行为$\red{k}$和$\red{n}$，随后$\red{n}$行为区间的左右端点，左右端点的绝对值不超过$\red{10 000}$。

输出格式

第一行为一个整数$\red{m}$，表示最少广告数，随后$\red{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