题目描述

某座豪宅发生了一起谋杀案。现场有 $N$ 名嫌疑人，分别称为 $1$ 号人物，$2$ 号人物，$\ldots$，$N$ 号人物。

第 $i$ 号人物在时间 $S_i$ 进入豪宅，在时间 $T_i$ 离开豪宅，且在其他任何时间都没有进出过豪宅。

关于这起案件，已知以下事实：

• 凶手恰好有两人。
• 案件从某个整数时间 $x$ 开始，耗时 $D$ 个单位时间，并在时间 $x + D$ 结束。
• 两名凶手在案件从开始到结束的整个期间内，都一直待在豪宅中。
  • 他们可以在案件开始的那一刻恰好进入豪宅，或在案件结束的那一刻恰好离开。

假设两名凶手都在这 $N$ 名嫌疑人之中，请问可能的「两名凶手组合」与「案件开始时间」的组合共有多少种？（注：两名凶手的先后顺序不作区分。）

输入格式

N D
S_1 T_1
S_2 T_2
...
S_N T_N

输出格式

输出一个整数，表示可能的「两名凶手组合」与「案件开始时间」的总组合数。

输入示例 1

3 2
1 5
2 4
3 5

输出示例 1

2

示例 1 说明

• $1$ 号人物在豪宅中的时间段为 $[1, 5]$，作案的可能开始时间为 $[1, 3]$。
• $2$ 号人物在豪宅中的时间段为 $[2, 4]$，作案的可能开始时间为 $[2, 2]$。
• $3$ 号人物在豪宅中的时间段为 $[3, 5]$，作案的可能开始时间为 $[3, 3]$。

各开始时间的可作案人数：

「凶手组合」数即 $\binom{cnt[t]}{2}$，分别为 $0, 1, 1$，总和为 $2$。

输入示例 2

2 1
1 10
3 7

输出示例 2

4

示例 2 说明

• $1$ 号作案开始时间范围 $[1, 9]$。
• $2$ 号作案开始时间范围 $[3, 6]$。

只有当 $t \in [3, 6]$ 时两人才同时可作案，共 $4$ 个时刻，每个时刻贡献 $1$ 对凶手。

输入示例 3

4 3
1 5
2 6
3 7
4 8

输出示例 3

3

示例 3 说明

每个人作案开始时间范围长度为 $T_i - S_i - D + 1 = 2$。相邻时间段两两相交，每次相交贡献 $1$ 对。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le S_i < T_i \le 10^6$
• $1 \le D \le 10^6$
• 所有输入值均为整数