题目描述

给你一个 $n$ 行 $m$ 列的矩阵 $S$，第 $i$ 行中，只有 $l_i$ 到 $r_i$ 的方格是 $1$，其它位置均为 $0$。换句话说，即 $s_{i,j} =1\ (1≤i≤n,l_i≤j≤r_i)$，剩余位置为 $0$。

现在我们规定，$(a,b)$ 是一个好点对，当且仅当：

• $∑_{i=1}^n ∑_{j=a}^b s_{i,j} >0$。
• 对于第 $i$ 行，$∑_{j=a}^b s_{i,j}$ 为 $0$ 或奇数。

求出所有好点对 $(a,b)$ 的 $b−a+1$ 的总和。

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 2\cdot 10^5$。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，$1\le l_i\le r_i\le m$。

输出格式

输出一个整数表示答案。

1 5
2 4

23

3 6
2 4
3 6
4 4

19