1435 - [NOIP 2005] 改编:多米诺骨牌
Description

稠州中学信奥社团的成员们在玩一种新式的多米诺骨牌:游戏开始前,需要将所有多米诺骨牌连接成长度为 L 分米的一条直线,每两张相邻的骨牌之间的间隔是 1 分米。如果将放多米诺骨牌的直线看成一个数轴,一端的骨牌放在数轴 0 的位置,另一端放在数轴 L 的位置。数轴上的每个整数点,即 0,1,2,3,4......L 都放了一张多米诺骨牌。由于有些区域的多米诺骨牌需要抽走另作他用,这些区域用它们在数轴上的起点和终点表示。已知任一区域的起点和终点的坐标都是整数,区域之间可能有重合的部分。你的任务是:计算将这些区域的骨牌移走后,直线上还有多少张骨牌。

Input

第一行有两个整数,分别表示直线的长度 L 和区域的数目 n 。

接下来 n 行,每行两个整数 x  和 y,表示一个区域的起点和终点的坐标。




Output

输出一个整数,表示将这些骨牌都抽走后,直线上剩余的骨牌数量。

Examples

Input

500 3
150 300
100 200
470 471

Output

298
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 9
通过次数 8