测试数据来自 system/1460

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(N\) （为奇数）堆干草，按 \(1..N\) 编号，开始时每堆高度都是 \(0\)。

　　FJ给出 \(K\) 条指令，每条指令包含两个用空格隔开的整数，例如 “ \(10\ 13\) ”，表示给 \(10,11,12,13\) 这四堆干草分别叠加一捆干草，即高度均增加 \(1\)。

　　FJ想知道，干草对完后，这 \(N\) 堆干草高度的中位数是多少。

【输入格式】

　　第 \(1\) 行：两个整数，分别是 \(N\) 和 \(K\)。
　　第 \(2..N+1\) 行：每行两个整数 \(A\) 和 \(B（1 ≤ A ≤ B ≤ N ）\) ，表示一条指令。

【输出格式】

　　一个整数，表示中位数。

【输入输出样例】

　Input

7 4
5 5
2 4
4 6
3 5

　Output

1

【输入输出样例说明】

　　堆完后，高度分别是 \(0,1,2,3,3,1,0\)。排序后为 \(0,0,1,1,2,3,3\)，故中位数是 \(1\)。

【数据说明】

　　对于 \(100\%\) 的数据，\(1 ≤ N ≤ 10^6\)，\(1 ≤ K ≤ 25000\)

【来源】

　　Mr.he