← 返回题目列表

Codeforces · 762/E

E. 广播电台

中文机器翻译题面 查看原题

在坐标线的格点中有n个广播电台,其中第i个由三个整数描述:

- xi — 线路上第 i 个站点的坐标,
- ri — 第 i 个电台的广播范围,
- fi — 第 i 个电台的广播频率。

如果编号为 i 和 j 的两个无线电台的广播范围大于或等于它们之间的距离,则我们会说它们彼此到达。换句话说,min(ri, rj) ≥ |xi - xj|。

如果 i < j,电台 i 和 j 相互到达且频率接近,则称一对广播电台 (i, j) 为坏电台,即 |fi - fj| ≤ k。

查找不良广播电台对的数量。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — 广播电台的数量以及相互到达的电台对的最大频率差被视为不良。

接下来的 n 行是广播电台的描述。每行包含三个整数 xi、ri 和 fi (1 ≤ xi, ri ≤ 109, 1 ≤ fi ≤ 104) — 第 i 个广播电台的坐标、广播范围和广播频率。没有两个广播电台会共享一个坐标。

输出

输出坏电台对的数量。

示例

输入 #1

3 2
1 3 10
3 2 5
4 10 8

输出 #1

1

输入 #2

3 3
1 3 10
3 2 5
4 10 8

输出 #2

2

输入 #3

5 1
1 3 2
2 2 4
3 2 1
4 2 1
5 3 3

输出 #3

2

输入#4

5 1
1 5 2
2 5 4
3 5 1
4 5 1
5 5 3

输出#4

5