Mr. Moneybag's Money Piles Mr. Moneybags is a very rich man. He has an assistant Mr. Perfect, who one day, got very mad, and shredded some of Mr. Moneybag’s $100 bills! Mr. Moneybags decided to punish Mr. Perfect. 

Mr. Moneybags tells Mr. Perfect to stack his money into different piles. 

He starts with N (1 &lt;= N &lt;= 1,000,000, N odd) empty stacks, numbered 1..N. Mr. Moneybags then gives him a sequence of K instructions (1 &lt;= K &lt;= 25,000), each of the form "A B", meaning that Mr. Perfect should add one new bill to the top of each stack in the range A to B, inclusive.  For example, if Mr. Perfect is told "11 13", then he should add a bill to each of the stacks 11, 12, and 13.

After Mr. Perfect finishes stacking the money according to his instructions, Mr. Moneybags would like to know the median height of his N stacks -- that is, the height of the middle stack if the stacks were to be arranged in sorted order (N is odd, so this stack is unique).  Please write an efficient program to help Mr. Perfect determine the answer to Mr. Moneybag’s question.

INPUT FORMAT:


Line 1: Two space-separated integers, N K.
Lines 2..1+K: Each line contains one of Mr. Moneybag’s instructions in the form of two space-separated integers A B (1 &lt;= A &lt;= B &lt;= N).


SAMPLE INPUT:

7 4                                                                             
5 5                                                                             
2 4
4 6
3 5


INPUT DETAILS:

There are N=7 stacks, and Mr. Moneybags issues K=4 instructions.  The first instruction is to add a bill to stack 5, the second is to add a bill to each stack from 2..4, etc.

OUTPUT FORMAT:


Line 1: The median height of a stack after Mr. Perfect completes the
   instructions.


SAMPLE OUTPUT:

1

The winner is the one with the "most efficient" algorithm. So, if someone posts an O(N) solution, then it will beat any O(N^2). If there is a tie, aka, two or more people who post an O(N) solution, for example, then whoever has is the shortest code (code-golfed) wins. 

So, your purpose is to write a efficient algorithm, and to prevent possible ties with other people, try to code-golf it as well. 

Another thing, the input is to be read from a file and the output must be written to a file.

EDIT
Also, the solution must be returned under or equal to 2 seconds. If it is not, you will receive a T. A wrong answer is an X. Which means, if no one can get it under time, then the most efficient algorithm sigh score of T can win. 

EDIT #2
Here are some more samples:


http://pastebin.com/x88xAyPA
http://pastebin.com/y6Cuxm7W
http://pastebin.com/kgbeiQtd


EDIT #3
Bonus: (subtract 100 chars from total)

Solve this under 2 seconds :)


http://pastebin.com/3uT9VSzv
O(K log N), many characters of Python

Edit: Improved by replacing merge sort with radix sort.

This is an improvement over my previous answer, but I'm posting it separately because it's a different strategy, and so the post doesn't get super-long. 

This is now optimal because simply reading the input can take 2*K*lg N time in the worst case -- 2*K numbers each with lg N bits.

The goal is to have minimal dependence on N. To do this, rather than store counts for each pile index, we realize that all piles in a contiguous cluster unaffected by the endpoints of any interval must have the same counts. So, if we see that an interval starts with 5, and there's no changes until 15, then those 10  piles have the same value.

Each change in pile size from a pile to the next one is caused by an interval starting or ending. We call these "events". Each event increases or decreases the current pile size by 1. If, from one event to the next, there's some number of piles, each of those piles has the current size.

We extract the 2*k events from the intervals, and sort them using a radix sort, taking advantage of the values being 1 through N. This take takes O(K*log(N)) because the numbers have O(lg N) bits.  

We then run over the events, and for each one, update the list of counts to the previous event, which requires adding a number up to N (so lg N bits). This takes O(log(N)) per step, and so O(K*log(N))

Finally, having gotten the counts of the pile sizes, it's easy to quickly find the median by computing the cumulative number of piles up to a given size (or, rather, we subtract it from our desired count). This also takes O(K*log(N)).

The algorithm does the huge test case in under a second.

The code (ungolfed) is below with comments.

# Process input
def get_ints(line):
 vals = line.split()
 return (int(vals[0]),int(vals[1]))

s = input()

lines = s.split("\n")
N,K = get_ints (lines[0])
intervals = [get_ints(line) for line in lines[1:]]

mins,maxes=map(list,zip(*intervals))

#Each event will represent an increase or decrease of a pile from the previous one
#Each min increases the count by 1
#Each max causes the count to decrease by 1, starting with the next pile
events = [(a,1) for a in mins] + [(b+1,-1) for b in maxes]
events.append((N+1,0))

#Do a radix sort on the first element of each pair 
#Each number has O(lg N) digits, so this takes O(k lg N) 
events.sort()

#Count of the number of piles of each size
#pile_sizes[size] counts the number of piles of that size
pile_sizes = [0]*K
cur_pile = 1
cur_size = 0

#For each event, we track the pile size after the event
#Then, on the next event, we know there were some number of piles of that size
#The number of piles equals the distance between events
#Multiple events on the same pile have zero distance and don't affect the counts
for event in events:
 event_pile = event[0]
 piles_current_size = event_pile - cur_pile
 pile_sizes[cur_size] += piles_current_size
 cur_pile = event_pile
 cur_size += event[1]

#Get the i_th largest pile size from a list of pile size counts
def get_order_stat(counts,i):
 for val in range(len(counts)):
  cur_count = counts[val]
  if i&lt;cur_count:
   return val
  i-=cur_count
 return None

median = get_order_stat(pile_sizes,N//2)

print(median)