题目描述

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

完成所有工作后，这 $N$ 个区域按砖数排序后排在中间位置的区域的砖的数目，即求砖数的中位数。请编程完成这个问题。

输入格式

第一行，两个用空格隔开的整数 $N$ 和 $K$。

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

输出格式

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

7 4 
5 5
2 4
4 6
3 5

1

数据规模与约定

$1\le A\le B\le N\le10^6,1\le K\le2.5\times10^4$，保证 $N$ 为奇数。