1024: 堆积干草

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:264 通过:80

题目描述

约翰的其中一头奶牛贝里斯最近非常为他自己的行为感到愧疚,因为他经常给约翰捣乱!于是他决定帮助约翰摆放新进来的一批干草。
开始的时候,总共有N(N一定是奇数)个空的器皿,编号从1到N。约翰给予了贝里斯K条命令来摆放干草。每条命令的形式都是:A B,意思是贝里斯应该把编号为A到B的器皿中每个都添加一束干草。例如,如果约翰的命令是:10 13,那么贝里斯应该在编号为10到13的器皿中各加入一束干草。
在贝里斯执行完这K条命令之后,约翰想要知道所有器皿中干草数量的中位数。这个中位数就是:把每个器皿中的干草数量从小到大排序之后,最中间的那个干草数量就是中位数(即排序后第(N+1)/2位置上的数)。
请帮助贝里斯计算这个中位数。

输入格式

第一行两个正整数N和K,表示N个器皿和K条命令。
接下来第2行到第K+1行,每行两个正整数,表示命令。

输出格式

输出这个中位数。

输入样例 复制

7 4 
5 5
2 4 
4 6 
3 5 

输出样例 复制

1

数据范围与提示

数据范围:1<=N<=1000000,1<=K<=25000,1<=A<=B<=N。
说明:贝里斯放好以后每个器皿中干草的数量分别是0,1,2,3,3,1,0,排序后是0,0,1,1,2,3,3,中间第四个位置上的1就是中位数。