Haybale Stacking

Time limit1sMemory limit128 MB

Summary

Add one bale to every stack in each given range, then report the median height among all N stacks.

Level: Medium4 of 10
Topics: Prefix sum, Array, Sorting, Implementation
Solved: No attempts yet

Problem

Feeling sorry for all the mischief she has caused around the farm recently, Bessie has agreed to help Farmer John stack up an incoming shipment of hay bales.

She starts with $N$ empty stacks, numbered $1$ through $N$ ( $1 \le N \le 1000000$ , and $N$ is odd). Farmer John then gives her a sequence of $K$ instructions ( $1 \le K \le 25000$ ), each of the form " $A$ $B$ ", meaning that Bessie should add one new hay bale to the top of every stack in the range $A \ldots B$ . For example, if Bessie is told " $10$ $13$ ", she adds one hay bale to each of the stacks $10$ , $11$ , $12$ , and $13$ .

After Bessie finishes following all of the instructions, Farmer John would like to know the median height of his $N$ stacks — that is, the height of the middle stack when the stacks are arranged in sorted order. Since $N$ is odd, this stack is unique. Please help Bessie determine the answer.

Input

Line 1: Two space-separated integers, $N$ and $K$ .
Lines $2 \ldots K+1$ : Each line contains one instruction as two space-separated integers $A$ $B$ ( $1 \le A \le B \le N$ ).

Output

A single line containing the median stack height after Bessie completes all instructions.

Hint

Consider the case with $N = 7$ stacks and $K = 4$ instructions. After all instructions are processed, the stack heights are $0, 1, 2, 3, 3, 1, 0$ . Sorting them gives $0, 0, 1, 1, 2, 3, 3$ , and the middle (fourth) value is $1$ , so the median is $1$ .

Examples5

Example 1
Input
```
7 4
5 5
2 4
4 6
3 5
```
Expected output
```
1
```
Example 2
Input
```
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
3 1
1 1
```
Expected output
```
0
```
Example 4
Input
```
5 2
1 5
1 5
```
Expected output
```
2
```
Example 5
Input
```
5 3
1 3
3 5
2 4
```
Expected output
```
2
```