1943: 广告问题

【题目描述】

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

【输入格式】

第一行为一个整数k和n。

随后n行为区间的左右端点，左右端点的绝对值不超过10 000。

【输出格式】

输出一个整数m，表示最少广告数。

【输入样例】

5 10

1 10

20 27

0 -3

15 15

8 2

7 30

-1 -10

27 20

2 9

14 21

【输出样例】

19

第一行为一个整数k和n。

随后n行为区间的左右端点，左右端点的绝对值不超过10 000。

5 10

1 10

20 27

0 -3

15 15

8 2

7 30

-1 -10

27 20

2 9

14 21

19