Radio stations

2000ms

262144K

Description:

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

x_i — the coordinate of the i-th station on the line,
r_i — the broadcasting range of the i-th station,
f_i — 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(r_i, r_j) ≥ |x_i - x_j|.

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, |f_i - f_j| ≤ k.

Find the number of bad pairs of radio stations.

Input:

The first line contains two integers n and k (1 ≤ n ≤ 10⁵, 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 x_i, r_i and f_i (1 ≤ x_i, r_i ≤ 10⁹, 1 ≤ f_i ≤ 10⁴) — 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.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF762E