题目描述

The new high-speed highway M-11 is an infinite straight line.

On the highway, there are $n$ stopping points, each of which is a rest area or a gas station. Each stopping point is defined by its coordinate $x_i$, and no two stopping points are located at the same place. A triplet of stopping points $(i, j, k)$ is called $\textit{convenient}$ if $x_{i} < x_{j} < x_{k}$, there are gas stations at points $x_{i}$ and $x_{k}$, a rest area at point $x_{j}$, and the distance between the gas stations does not exceed $d$.

A team from Moscow is planning to travel to the contest along the M-11 highway, and its leader became curious about how many convenient triplets of stopping points exist along the way.

输入格式

The first line contains two natural numbers $n$ and $d$ --- the number of stopping points and the maximum distance between gas stations ($3 \leq n \leq 5 \cdot 10^{5}$, $2 \leq d \leq 10^{9}$).

In the following $n$ lines, the stopping points are given. Each stopping point is defined by two integers $x_i$ and $t_i$ --- the coordinate of the point and its type. Type $0$ denotes a rest area, and type $1$ denotes a gas station ($-10^{18} \leq x_i \leq 10^{18}$; $t_{i} \in \{0, 1\}$). It is guaranteed that the coordinates of the stopping points are in increasing order.

输出格式

Output a single number --- the number of convenient triplets.

8 5
1 1
2 0
3 1
6 0
7 0
8 1
15 1
19 1

3

10 6
0 1
1 0
3 1
4 0
5 1
8 1
10 0
11 0
14 1
18 1

7

提示

In the first input set, the convenient triplets are $(1, 2, 3)$, $(3, 4, 6)$, and $(3, 5, 6)$.