Submit solution

Points:
5

Time limit:
1.0s

Memory limit:
256M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Bob wants to build a house along a river. Unfortunately some parts of the river are occupied by animals and cannot be used. Please write a program to help Bob to calculate the length of the longest continuous river segment that is **NOT** occupied by any animals.

You can think of the river as a line of length from position to position . There are animals, each animal occupies a continuous river segment from position to . Note that the segments occupied by animals may be overlapping. Output if the whole river is occupied by animals.

#### Input Specification

- The first line contains an integer that represents the length of the river.
- The second line contains an integer that represents the number of animals.
- Following are lines. Each line contains two integers and that represent the river segment occupied by one animal.

#### Output Specification

The length of longest continuous river segment that is not occupied by any animals.

#### Sample Input 1

```
5
2
0 2
3 5
```

#### Output for Sample Input 1

`1`

#### Sample Input 2

```
10
2
2 5
4 7
```

#### Output for Sample Input 2

`3`

#### Sample Input 3

```
10
2
0 5
5 10
```

#### Output for Sample Input 3

`0`

#### Explanation

For Sample 1, as 0-2 and 3-5 are occupied, the only remaining part is 2-3.

For Sample 2, the remaining parts are 0-2 and 7-10.

## Comments

For anyone that cannot seem to solve all the test cases, the segment occupied by the animal is from [s, t) (from s to t - 1).