题目来自第 29 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 3.0 秒

空间限制： 1024 MB

题目描述

春天到了，西西艾弗岛上的 $n$ 块田地需要施肥了。$n$ 块田地编号为 $1, 2, \cdots, n$，按照编号从小到大的顺序排成一列。

为了给田地施肥，顿顿准备了 $m$ 辆施肥车。但是由于土地的松软程度不同，施肥车的质量不一，不一定每一辆施肥车都能给每一块田地施肥。其中，第 $i$ 辆施肥车只能恰好从第 $l_i$ 块田地开到第 $r_i$ 块田地，并给编号在 $l_i$ 与 $r_i$ 之间的田地（包含 $l_i$ 和 $r_i$）都施一遍肥。其中 $1 \leq l_i < r_i \leq n$。

顿顿希望制定一个施肥的计划。首先，他将选定二元组 $(L, R)\ (1 \leq L < R \leq n)$，并选择只给编号在 $L, R$ 之间（包含 $L, R$）的田地施肥。接着，他会从使用这 $m$ 辆施肥车中的一部分（或全部）对田地施肥。他想要保证：编号在 $L$ 和 $R$ 之内的田地至少被某一辆施肥车施了一次肥，且编号范围外的田地都没有被施过肥。

现在，他想知道，他能够选择多少种不同的二元组 $(L, R)$ 作为施肥范围，使得可以选出一部分（或全部）施肥车，完成他的目标。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n, m$，表示田地的块数和施肥车的辆数。

接下来 $m$ 行，第 $i$ 行输入两个正整数 $l_i, r_i$，表示第 $i$ 辆施肥车的施肥范围从第 $l_i$ 块田地到第 $r_i$ 块田地。

输出格式

输出到标准输出。

输出一个正整数，表示顿顿能够选择多少种不同的二元组 $(L, R)$ 作为施肥范围，使得他可以选出一部分（或全部）施肥车，完成他的目标。

4 3
1 2
3 4
2 3

6

样例 1 解释

在这组样例中，顿顿可以选择 $6$ 种不同的二元组 $(L, R)$。

第一种：选择 $(L, R) = (1, 2)$，并只选取第 $1$ 个施肥车施肥。

第二种：选择 $(L, R) = (3, 4)$，并只选取第 $2$ 个施肥车施肥。

第三种：选择 $(L, R) = (2, 3)$，并只选取第 $3$ 个施肥车施肥。

第四种：选择 $(L, R) = (1, 4)$，并选取第 $1$ 个和第 $2$ 个施肥车施肥。

第五种：选择 $(L, R) = (1, 3)$，并选取第 $1$ 个和第 $3$ 个施肥车施肥。

第六种：选择 $(L, R) = (2, 4)$，并选取第 $2$ 个和第 $3$ 个施肥车施肥。

样例 2

见题目文件区的 2.in 与 2.ans。

样例 2 解释

该样例满足子任务 1 的限制。

样例 3

见题目文件区的 3.in 与 3.ans。

样例 3 解释

该样例满足子任务 2 的限制。

样例 4

见题目文件区的 4.in 与 4.ans。

样例 4 解释

该样例满足子任务 3 的限制。

样例 5

见题目文件区的 5.in 与 5.ans。

样例 5 解释

该样例满足子任务 4 的限制。

样例 6

见题目文件区的 6.in 与 6.ans。

样例 6 解释

该样例满足子任务 5 的限制。

样例 7

见题目文件区的 7.in 与 7.ans。

样例 7 解释

该样例满足子任务 6 的限制。

子任务

对于所有数据，保证 $2 \leq n \leq 2 \times 10^5,\ 1 \leq m \leq 2 \times 10^5,\ 1 \leq l_i < r_i \leq n$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$m\le$	特殊性质
1	15	$18$		$\times$
2	10	$50$
3		$400$
4	25	$3000$
5	15	$2\times 10^5$		$\checkmark$
6	25			$\times$

特殊性质：保证任意两个施肥车的施肥范围不存在相互包含的关系，也就是说，对任意 $1 \leq i < j \leq m$，$l_i < l_j, r_i < r_j$ 或 $l_i > l_j, r_i > r_j$。