Problem
One day, as punishment for pranks and deceit, Aunt Polly made Tom paint a
L yard fence. All of you remember very well that Tom sold (for various goodies) his work to other boys who wanted to whitewash the fence.
By the time Tom ran out of lime, the fence had been painted by
N boys. And since Tom didn’t really follow the boys, everyone painted the part of the fence that he liked best.
Each
i-th boy started painting the fence from a vertical plank with coordinate
Lefti and painted up to plank with coordinate
Righti (the length of the board is considered equal to 1).
Determine the length of the fence that Tom will need to paint himself.
Input
The first line contains the number L - the length of Aunt Polly's fence. The second line contains the number N, the next N lines - pairs Lefti< /sub> and Righti. All numbers are integers
Restrictions:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).
Imprint
Print a single number - the length of the fence that Tom needs to finish painting.
Examples
| # |
Input |
Output |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10
| 10 |
| 3 |
100
2
10 30
20 40
| 70 |