Description
为了表达最近在农场上制造的一些恶作剧的歉意，奶牛Bessie打算帮助Farmer John堆放一些干草包。
干草堆的数量是N(1≤N≤1000000，N是奇数)，编号是1...N，开始时这些干草堆都是空的，没有干草包。FJ会给Bessie一组指令，指令的个数是K，指令的格式是“A B”，指令的意思是Bessie应该给编号为A到B的干草堆增加一个干草包。
例如，如果指令是“10 13”，那么Bessie应该给编号为10,11,12,13的干草堆各增加一个干草包。
当Bessie执行完所有的指令后，FJ想知道这N堆干草堆高度的中间值是多少，也就是如果把这N个干草堆按照高度排序，序列的中间值是多少？
因为N是奇数，所以中间值是惟一的。请帮助Bessie计算出答案。
Input
第一行，用空格隔开的两个整数分别表示N和K（1≤N≤1000000；1≤K≤25000）
接下来K行，表示FJ的K个指令，格式是“A B”，其中1≤A≤B≤N
Output
输出一行，一个整数，表示N个干草堆高度的中间值
HINT
样例说明：
一共有7个干草堆，执行完4个指令后，这7个干草堆的高度分别是0,1,2,3,3,1,0.按照升序排序后是0,0,1,1,2,3,3，所以干草堆高度的中间值是1。