Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

A. Counting Subarrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an integer $$$N$$$ which is the length of an array and also given $$$M$$$ Subarrays. You need to find the number of good non-empty subarrays in the array. A subarray is considered $$$Good$$$ if it doesn't fully contain any of the $$$M$$$ given subarrays. In other words, for every "Good" subarray $$$[a,b]$$$, there should not exist an $$$i$$$ such that $$$a \leq l_i$$$ and $$$r_i \leq b$$$.

Input

The first line contains a single integer $$$N ( 1 \le N \le 10^9)$$$, the length of the array. The second line contains a single integer $$$M ( 1 \le M \le 3 \times 10^5)$$$ , the number of ranges. Each of the next $$$M$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ separated by a single space, indicating the range of the $$$i_th$$$ subarray. $$$(1 \le l_i \le r_i \le N)$$$

Output

Output a single integer, the total number of $$$Good$$$ $$$Subarrays$$$.

Example
Input
6 3
1 3
2 3
5 5
Output
7
Note

For the sample test case, the good subarrays are (1,1) , (2,2) , (3,3) , (4,4) , (6,6) , (1,2) , (3,4).