G. M-11 Highway
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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 convenient if $$$x_{i} \lt x_{j} \lt 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.

Input

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

Output a single number — the number of convenient triplets.

Examples
Input
8 5
1 1
2 0
3 1
6 0
7 0
8 1
15 1
19 1
Output
3
Input
10 6
0 1
1 0
3 1
4 0
5 1
8 1
10 0
11 0
14 1
18 1
Output
7
Note

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