You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

玩着玩着小 X 觉得有点饿了， 他想出门买些吃的。 刚刚走出大门，小 X 就看到有位大叔在做煎饼，而且做法十分有趣。只见此人将 n 块煎饼排成一排，手持一把大铲，将煎饼铲得上下翻飞， 煞是好看。 小 X 顿时食指大动， 赶紧走上前去细细打量，发现此人做煎饼还十分的讲究，在做的过程中，大叔每次会将从第 x 块煎饼开始到第 y 块煎饼结束的这 y−x+1 块煎饼全部翻个个儿（正面翻到反面， 反面翻到正面）。而他每次会选择不同的区间（区间是指连续的一段煎饼，如 3,4,5,6四块煎饼用区间 [3,6]表示）来翻这些煎饼。每块煎饼都有正反两面， 开始时这些煎饼都是反面朝上。此人一共翻了 m 次煎饼，看得小 X 眼花缭乱。 但是小 X 很想知道这 n 块煎饼到最后一共有多少块是正面朝上的， 于是他只好求助于你了。

Format

Input

第一行包含两个用空格隔开的正整数表示 n 和 m 。 接下来 m 行每行两个用空格隔开的正整数 x 和 y， 表示每次将区间 [x，y] 中的 y−x+1 块煎饼翻个个儿。 开始时这 n 块煎饼都是反面朝上（提示： 可以用 0 表示煎饼的反面，1 表示煎饼的正面）

Output

输出仅有一行包含一个整数 ans ， 表示最后有 ans 块煎饼是正面朝上的。

Samples

10 5
1 8
5 6
1 9
3 8
2 7

5

Limitation

样例解释】

共有 10 块煎饼， 开始时状态为“反反反反反反反反反反”，

第一次操作将区间 [1，8] 的煎饼翻个身，状态变成“ 正正正正正正正正反反”， 红色表示翻的区间。

第二次操作将区间 [5，6] 的煎饼翻个身， 状态变成“正正正正反反正正反反”。

第三次操作将区间 [1，9] 的煎饼翻个身， 状态变成“ 反反反反正正反反正反”。

第四次操作将区间 [3，8] 的煎饼翻个身， 状态变成“反反正正反反正正正反”。

第五次操作将区间 [2，7] 的煎饼翻个身， 状态变成“反正反反正正反正正反”。

最后共有 5 块煎饼正面朝上。

【数据范围】

对于 30% 的数据， 1≤n,m≤100，1≤x≤y≤n；

对于另外 30% 的数据， 1≤n≤1000000 ，1≤m≤100000， x=1, 1≤y≤n；

对于另外 40% 的数据， 1≤n≤1000000，1≤m≤100000，1≤x≤y≤n；