可疑的区间

可疑的区间

题号：NC235686
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给出 $n$ 个有趣的区间 $[L_1,R_1],[L_2,R_2],...,[L_n,R_n]$ ，编号分别为 $1\sim n$ 。给出一个整数 $len$ ，对于任意一段长度为 $len$ 的区间 $[l,r],(r-l+1=len)$ ，其中 $l$ 是正整数。其有趣值的定义为：与 $[l,r]$ 有交集的有趣的区间个数。其权重的定义为：与 $[l,r]$ 有交集的有趣的区间编号的总和。

例如有 $3$ 个有趣的区间 $[1,3],[2,4],[5,6]$ ，编号分别为 $1\sim 3$ 。 $[2,3]$ 的有趣值为 $2$ ( $[2,3]$ 与 $[1,3],[2,4]$ 有交集)，权重为 $1+2=3$ 。

牛牛选择了一段长度为 $len$ 的 $[l,r],(r-l+1=len)$ ，其中 $l$ 是正整数。牛牛会选择有趣值最大的区间，如果两个区间有趣值相同，那么牛牛会选权重最大的。

对于一段区间 $[l,r],r-l+1=len$ ，其中 $l$ 是正整数。可能被牛牛选择，那么这段区间就是可疑的，请输出可疑的区间的个数。

输入描述:

第一行包含两个整数 $n\ len\ (1\le n\le10^6,1\le len\le5\times10^6)$ ，表示有趣的区间的个数和选择区间的长度。

接下来 $n$ 行，每行包含两个整数 $L,R\ (1\le L\le R\le 5\times10^6)$ ，分别表示区间的左右端点。

输出描述:

输出包含一个整数，表示可疑区间的个数。

示例1

输入

复制

输出

复制

说明

$[1,2]$ ：和第 $1,2$ 个区间有交集，有趣值为 $2$ ，权重为 $3$ 。

$[2,3]$ ：和第 $1,2$ 个区间有交集，有趣值为 $2$ ，权重为 $3$ 。

$[3,4]$ ：和第 $1,2$ 个区间有交集，有趣值为 $2$ ，权重为 $3$ 。

$[4,5]$ ：和第 $2,3$ 个区间有交集，有趣值为 $2$ ，权重为 $5$ 。

$[5,6]$ ：和第 $2,3$ 个区间有交集，有趣值为 $2$ ，权重为 $5$ 。

其余长度为 $2$ 的区间有趣值都小于 $2$ 。

有 $2$ 个可疑区间 $[4,5]$ 和 $[5,6]$ 。