堆砖游戏 描述

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

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

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

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

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

输入样例 1

7 4 5 5 2 4 4 6 3 5 输出样例 1

1 提示

1 ≤ � ≤ 1000000 1≤N≤1000000, � N为奇数。 1 ≤ � ≤ 25000 1≤K≤25000。 1 ≤ � ≤ � ≤ � 1≤A≤B≤N。