描述

开始给定 \(N\) ( \(N\) 为奇数)个单位的空地，分别以 \(1 \sim N\) 表示。给出一个有 \(K\) 个指令的序列，每个指令格式为"\(A\) \(B\)"，意味着在 \(A \sim B\) 的区域各增加一块砖。例如，如果给定区域为"\(10\) \(13\)"，那么将在区域 \(10,11, 12, 13\) 的位置各增加一个砖块。
完成所有工作后，这 \(N\)个区域按砖数排序后排在中间位置的区域的砖的数目，即求砖数的中位数（由于\(N\)为奇数，所以这个值是唯一的）。 请编程完成这个问题。

格式

输入格式

第一行两个用空格隔开的整数\(N\)和\(K\)。
第 \(2 \sim K+\)行，每行两个用空格隔开的整数 \(A\) 和 \(B\) 表示放砖的指令 (\(1≤A≤B≤N\))。

输出格式

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

样例1

输入样例1

7 4
5 5
2 4
4 6
3 5

输出样例1

1

限制

\(100\)%的数据：\(1≤N≤10^6,1≤K≤25000\)。