题目描述

一开始给定N（1≤N≤1000000，N为奇数）个单位的空地，分别以1-N表示。再给出一个有K个指令的序列（1≤K≤25000），每个指令格式为“A B”，意味着在A-B的区域各增加一块砖。例如，如果给定区域为“10 13”，那么将在区域10，11，12，13的位置各增加一个砖块。

请编程求出完成所有工作后，这N个区域按砖数排序后排在中间位置的区域的砖的数目，即求砖数的中位数（由于N为奇数，所以这个值是唯一的）

输入格式：

第一行，两个整数N和K，之间用一个空格隔开；

第二到K+1行，每行两个整数A和B,表示放砖的指令，之间用一个空格隔开。1≤A≤B≤N。

输出格式：

输出一行,一个整数，表示完成所有工作后，这N个区域按砖数排序后排在中间位置的区域的砖的数目。

输入样例1：

7 4

5 5

2 4

4 6

3 5

输出样例1：

1

样例解释：

数据规模：

对于70%的数据，N，K≤10000；

对于100%的数据，N≤1000000，K≤25000。