P13970 [VKOSHP 2024] M-11 Highway

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.

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