首页 > 试题广场 >

牛牛种树

[编程题]牛牛种树
  • 热度指数:36 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

牛牛在一条街道上准备种一批树,这个街道有n个种树的坑位,分别编号为1到n。牛牛雇佣了m个小牛进行种树,每一个小牛负责一组连续编号的树坑进行种植,小牛负责的连续编号表示为[a, b),a表示起始编号,b表示终止编号,注意种植的编号范围是左闭右开。如果小牛在种植的过程中发现某个坑位已经有树种好了,则跳过这个坑位后继续种植。问牛牛所负责的街道最终一共能够种下几棵树?返回这个结果。



输入描述:

第一行一个整数n表示街道的坑位数量,一个整数m表示小牛的数量,用空格隔开;

后m行每行两个数字ai,bi,用逗号隔开,表示对应的小牛所负责的种树编号范围[ai,bi)。



输出描述:

输出一个整数,表示最后一共能种下几棵树。

示例1

输入

10 3
1,5
3,7
6,10

输出

10