Haybale Stacking

Беси согласилась помочь ФД уложить пакеты с сеном.
Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков,
пронумерованных от 1 до N. Затем ФД дает ей последовательность из 
K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что
Беси должна добавить по одному пакету с сеном в каждый из стеков 
в диапазоне от A до B. Например, инструкция 10 13 означает, что 
Беси должна положить по пакету  сеном в стеки 10, 11, 12, 13.

После того как вся работа закончена, ФД хочет узнать медианную высоту
всех N своих стеков - то есть высоту среднего стека, если все стеки 
упорядочить по высоте. По условию N нечетно, поэтому этот стек 
уникален. Пожалуйста, помогите Беси ответить на этот вопрос. 

PROBLEM NAME: stacking

INPUT FORMAT:

* Строка 1: Два разделенных пробелом целых числа, N K.

* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в 
                 виде двух целых (разделенных пробелом) чисел A B 
                 (1 <= A <= B <= N).
                      
SAMPLE INPUT (файл stacking.in):

7 4
5 5
2 4
4 6
3 5

INPUT DETAILS:

Всего N=7 стеков, и FJ дал K=4 инструкции.  Первая инструкция 
- добавить пакет с сеном в стек 5, вторая - добавить по пакету с сеном 
в стеки 2 : 4     и т.д.


OUTPUT FORMAT:

* Строка 1: Медианная высота после того как Беси выполнит все инструкции


SAMPLE OUTPUT (файл stacking.out):

1

OUTPUT DETAILS:

После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0.  
Если их упорядочить, получим: 0,0,1,1,2,3,3.
Средний элемент равен 1.