CANDYSTRIPE2

We have (once again*) ~N~ chocolates, numbered from ~1~ to ~N~, wrapped and placed in a row like a filmstrip. Some of them have bitter chocolate, and some have sweet chocolate. Because our brother has a strong aversion to bitter chocolate, we placed a special order at the patisserie requesting the film to have few bitter chocolates and many sweet ones.

As proof that they fulfilled our request, the confectionery enumerates a set of ~M~ segments of the film, each described by two numbers ~L_i~ and ~R_i~, indicating the chocolates from position ~L_i~ to ~R_i~ (inclusive). They assure us that each of these segments contains exactly one bitter chocolate.

If the assurances of the patisserie are true, find out how many bitter chocolates can be at most in the film.

Input:

The first line of the input will contain two positive integers ~N~ and ~M~, separated by a space: the size of the film and the number of segments enumerated by the patisserie. Each of the next ~M~ lines corresponds to a numbered segment and contains two integers, ~L_i~ and ~R_i~, separated by a space.

Output:

The output should contain a single line with exactly one integer: the maximum number of bitter chocolates that can exist in the film, if the patisserie's guarantees are true. If there is no consistent answer according to the guarantees of the patisserie, the output should be the number ~-1~.

Constraints:

• ~1 \le N \le 200.000~ και ~1 \le M \le 100.000~
• ~1 \le L_i \le R_i \le N~
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB.
• For test cases with a total value of ~10%~, it will be ~N \le 20~ and ~M \le 20~.
• For test cases with a total value of ~30%~, it will be ~N \le 1000~ and ~M \le 2000~.
• For test cases with a total value of ~60%~, it will be ~N \le 10.000~ and ~M \le 10.000~.
• For test cases with a total value of ~65%~, it will be ~average(R_i - L_i) \le 20~.

Examples of Input - Ouput:

1st

input:

5 3
3 4
1 4
2 5

output:

1

2nd

input:

6 2
2 4
3 5

output:

4

3d

input:

4 3
1 4
2 2
3 3

output:

-1

Explanation of the examples:

In the first example, there can only be one bitter chocolate, either at position ~3~ or position ~4~. In the second example, there can be four bitter chocolates at positions ~1~, ~2~, ~5~, and ~6~. In the third example, the last two segments guarantee that there are bitter chocolates at positions ~2~ and ~3~. However, the first segment guarantees that there is only one bitter chocolate between positions ~1~ and ~4~. These guarantees cannot all be true simultaneously.

• The solution to this problem is not related to yesterday's candystripe problem- only the story has similarities.