题目描述

Bessie 对她自己最近在农场周围的恶作剧感到抱歉，于是她同意帮助 Farmer John 堆叠新送达的一批干草捆。开始时有 $N$（$N$ 是奇数）个空草堆，标记为 $1\ldots N$。FJ 将会给 Bessie 包含 $K$ 条指令的序列，每条指令的格式为 $A\ B$，表示 Bessie 应该在草堆 $A\ldots B$ 中每一个草堆顶部新放一捆干草。

例如，如果 Bessie 听到指令 $10\ 13$，那么她应该在草堆 $10,11,12,13$ 上各新放一捆干草。

在 Bessie 完成了 FJ 的所有指令后，FJ 想要知道 $N$ 个草堆高度的中位数——也就是说，所有草堆排序后中央草堆（由于 $N$ 是奇数，这个草堆是唯一的）的高度。请帮助 Bessie 确定 FJ 问题的答案。

输入格式

第 $1$ 行：两个被空格分隔的整数 $N$ 和 $K$。

第 $2\ldots K+1$ 行：每行包含一条 FJ 的指令，其格式为两个被空格分隔的整数 $A$ 和 $B$。

输出格式

输出共一行一个整数，Bessie 完成所有指令后草堆高度的中位数。

7 4
5 5
2 4
4 6
3 5

1

3 1
1 3

1

5 3
1 1
2 4
5 5

1

样例说明

有 $N=7$ 个草堆，FJ 给出了 $K=4$ 条指令。完成任务后，草堆的高度为 $0,1,2,3,3,1,0$。高度的中位数是 $1$，因为 $1$ 是排序后结果 $0,0,1,1,2,3,3$ 的中间数。

数据范围与约定

• 对于 $20\%$ 的数据：$1\le N\le100$，$1\le K\le100$；
• 对于 $40\%$ 的数据：$1\le N\le1{,}000$，$1\le K\le5{,}000$；
• 对于 $60\%$ 的数据：$1\le N\le50{,}000$，$1\le K\le10{,}000$；
• 对于 $100\%$ 的数据：$1\le N\le1{,}000{,}000$，$1\le K\le25{,}000$，$1\le A\le B\le N$，且 $N$ 为奇数。