Book Piano Room

By Kay Akashi

Problem Statement

In the Music Centre, there is only one piano practice room. There are $n$ time slots in a single day available for the piano practice room.

One person is permitted to book several time slots in a day. The rule for booking is that, one firstly chooses consecutive time slots, and he/she can use practice rooms during those time slots where there's no preexisting booking.

Students and teaching staff love playing the piano, and today $m$ people are trying to book piano rooms. It is known that $i$-th person $(1 \leq i \leq m)$ would like to book a room between $l_{i}$-th time slot and $r_{i}$-th time slot inclusive.

Your task is to output the number of time slots in which the practice room is vacant.

Note that, $i$-th person can make bookings earlier than $(i + 1)$-th person does $(1 \leq i \leq n - 1)$.

Constraints

$1 \leq n, m \leq 10^{5}$, $1 \leq l \leq r \leq n$.

Subtask 1 (20%)

$1 \leq n, m \lt 100$.

Subtask 2 (80%)

$100 \leq n, m \leq 10^{5}$.

Input

The first line of input contains two integers, $n$ and $m$. Following are $m$ lines $i$-th of which contains two integers $l_{i}$ and $r_{i}$.

Output

Output the answer.

Examples

5 2
1 2
4 5

1

6 3
1 4
2 5
6 6

0