跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0932. Radio stations

  • ID: 938
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:提高
  • 上传者:
  • 二分
  • 数据结构
  • 算法思想
  • 提高
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Radio stations

题目描述

E. Radio stations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the lattice points of the coordinate line there are n radio stations, the i-th of which is described by three integers:

  • xi − the coordinate of the i-th station on the line,
  • ri − the broadcasting range of the i-th station,
  • fi − the broadcasting frequency of the i-th station.

We will say that two radio stations with numbers i and j reach each other, if the broadcasting range of each of them is more or equal to the distance between them. In other words min(ri,rj)≥|xi-xj|.

Let's call a pair of radio stations (i,j) bad if i<j, stations i and j reach each other and they are close in frequency, that is, |fi-fj|≤k.

Find the number of bad pairs of radio stations.

Input

The first line contains two integers n and k (1≤n≤105, 0≤k≤10) − the number of radio stations and the maximum difference in the frequencies for the pair of stations that reach each other to be considered bad.

In the next n lines follow the descriptions of radio stations. Each line contains three integers xi, ri and fi (1≤xi,ri≤109, 1≤fi≤104) − the coordinate of the i-th radio station, it's broadcasting range and it's broadcasting frequency. No two radio stations will share a coordinate.

Output

Output the number of bad pairs of radio stations.

Examples
Input
3 2
1 3 10
3 2 5
4 10 8
Output
1
Input
3 3
1 3 10
3 2 5
4 10 8
Output
2
Input
5 1
1 3 2
2 2 4
3 2 1
4 2 1
5 3 3
Output
2
Input
5 1
1 5 2
2 5 4
3 5 1
4 5 1
5 5 3
Output
5


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 368 题。保留原作者与原赛事署名。