Covering a Segment

Time limit2sMemory limit128 MB

Summary

Given up to 100,000 segments on a line, find the minimum number needed to fully cover [0, M], or output 0 if impossible.

Level: Medium5 of 10
Topics: Greedy, Intervals, Sorting
Solved: No attempts yet

Problem

Several segments are given on the x-axis. Each segment is written as [L_i, R_i], meaning that it starts at (L_i) and ends at (R_i). Choose some of these segments so that the whole interval [0, M] is covered. Find the minimum number of segments needed to cover [0, M] completely.

Input

The first line contains an integer (M)((1 \le M \le 50,000)). Each following line contains two integers (L_i) and (R_i)((|L_i|, |R_i| \le 50,000)) describing one segment. The segment list ends with 0 0. There are at most 100,000 segments.

Output

Print the minimum number of segments needed to cover [0, M] completely. If it is impossible, print 0.

Examples2

Example 1
Input
```
1
-1 0
0 1
0 0
```
Expected output
```
1
```
Example 2
Input
```
1
-1 0
-5 -3
2 5
0 0
```
Expected output
```
0
```