Festival

Andrei este pasionat de festivaluri și vrea să se bucure la maxim de cele $N$ festivaluri anunțate. Fiecare festival $i$ dintre cele $N$ este caracterizat prin trei valori: $T_i$ — timpul de start, $X_i$ — locația pe axa Ox și $S_i$ — satisfacția oferită de participarea la festivalul $i$.

Știm că Andrei poate începe de la orice festival și se poate deplasa între festivaluri folosind bicicleta, însă poate parcurge cel mult $D$ unități de distanță dintr-un singur drum, din cauza oboselii. Astfel, el poate merge de la festivalul $i$ la festivalul $j$ dacă sunt îndeplinite simultan următoarele trei condiții:

• $T_i \leq T_j$
• $|X_i - X_j| \leq D$
• $|X_i - X_j| \leq T_j - T_i$

Altfel spus, bicicleta lui Andrei se poate deplasa doar între festivaluri aflate la o distanță de cel mult $D$ și pentru care timpul dintre începuturile celor două festivaluri este suficient de mare pentru ca Andrei să poată ajunge (având în vedere că viteza bicicletei este de 1 unitate de lungime pe unitate de timp).

Determinați suma maximă a satisfacției care se poate obține participând la un grup de festivaluri, respectând condițiile.

Date de intrare

Fișierul de intrare festival.in conține pe prima linie numerele $N$ și $D$, iar pe următoarele $N$ linii câte trei numere întregi $T_i$, $X_i$ și $S_i$ ($1 \leq i \leq N$) reprezentând timpul de start, locația pe axa Ox și satisfacția oferită de participarea la festivalul $i$.

Date de ieșire

Fișierul de ieșire festival.out va conține un singur număr întreg, reprezentând suma maximă a satisfacției.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $0 \leq D \leq 1 \ 000 \ 000 \ 000$
• $0 \leq T_i, X_i, S_i \leq 1 \ 000 \ 000 \ 000$
• Oricare ar fi $i\neq j$, vom avea $T_i \neq T_j$ sau $X_i \neq X_j$
• Andrei consideră că participă la festival, dacă este acolo la momentul de început al festivalului.

Exemplul 1

festival.in

5 3
3 5 30
1 2 80
7 6 50
8 9 20
5 4 10

festival.out

140

Explicație

Pentru acest exemplu avem $N=5$ festivaluri și $D=3$.
Dacă Andrei începe cu festivalul $(1,2,80)$, atunci singurul festival care respectă condițiile de deplasare este $(5,4,10)$ (timpul crește, distanța $\leq$ 3, și distanța $\leq$ diferența de timp). Apoi, de la festivalul $(5,4,10)$ se poate duce doar la $(7,6,50)$ respectând aceleași condiții. Astfel, avem $(1,2,80)$ \textrightarrow $(5,4,10)$ \textrightarrow $(7,6,50)$ cu suma satisfacției 140. Nu există o modalitate de a obține o sumă mai mare.

Exemplul 2

festival.in

10 50
86 43 23
24 12 16
98 37 42
19 42 83
79 55 59
42 92 48
45 57 71
67 64 97
97 71 68
57 38 37

festival.out

378

Explicație

O modalitate de a obține suma 378 este $(19, 42, 83) \Rightarrow (45, 57, 71) \Rightarrow (67, 64, 97) \Rightarrow (79, 55, 59) \Rightarrow (97, 71, 68)$.