G. Трасса М-11
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Новая скоростная автомобильная магистраль М-11 представляет собой бесконечную прямую.

На трассе расположены $$$n$$$ остановочных пунктов, каждый из которых — зона отдыха или заправка. Каждый остановочный пункт задается своей координатой $$$x_i$$$ и при этом никакие два остановочных пункта не находятся в одном и том же месте. Тройка остановочных пунктов $$$(i, j, k)$$$ называется удобной, если $$$x_{i} \lt x_{j} \lt x_{k}$$$, в точках $$$x_{i}$$$ и $$$x_{k}$$$ расположены заправки, а в точке $$$x_{j}$$$ — зона отдыха, и при этом расстояние между заправками не превосходит $$$d$$$.

Одна команда из Москвы собирается поехать на ВКОШП по трассе М-11, и её руководителю стало интересно, сколько существует удобных троек остановок на пути.

Входные данные

В первой строке дано два натуральных числа $$$n$$$ и $$$d$$$ — количество остановочных пунктов и максимальное расстояние между заправками ($$$3 \leq n \leq 5 \cdot 10^{5}$$$, $$$2 \leq d \leq 10^{9}$$$).

В следующих $$$n$$$ строках даны остановочные пункты. Каждый остановочный пункт задается двумя целыми числами $$$x_i$$$ и $$$t_i$$$ — координата пункта и его тип. Тип $$$0$$$ обозначает зону отдыха, тип $$$1$$$ обозначает заправку ($$$-10^{18} \leq x_i \leq 10^{18}$$$; $$$t_{i} \in \{0, 1\}$$$). Гарантируется, что координаты остановочных пунктов идут в возрастающем порядке.

Выходные данные

Выведите единственное число — количество удобных троек.

Примеры
Входные данные
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
Примечание

В первом наборе входных данных удобными тройками являются $$$(1, 2, 3)$$$, $$$(3, 4, 6)$$$ и $$$(3, 5, 6)$$$.