from bisect import bisect_left, bisect_right from collections import deque def find_interval(slis: list, lo: int, hi: int) -> tuple[int, int, int]: """ ソート済み slis に対して、lo <= x <= hi を満たす要素の個数と範囲を返す Returns: 範囲内の個数, l, r """ assert lo <= hi l = bisect_left(slis, lo) r = bisect_right(slis, hi) count = r-l if count <= 0: return 0, -1, -1 # no interval return count, l, r-1 class RangeAddRangeMax: B = 512 # 一つのバケット幅 def __init__(self, a: list): n = len(a) bsize = (n + self.B - 1) // self.B # self.buckets = [0] * bsize self.add_buckets = [0] * bsize # バケットへの加算 self.max_buckets = [0] * bsize # バケットの最大値 self.data = a.copy() for i in range(bsize): start = i * self.B stop = min(n, (i+1) * self.B) self.max_buckets[i] = max([a[i] for i in range(start, stop)]) def range_add(self, l: int, r: int, x: int): """[l, r) に x を加算""" assert 0 <= l < r <= len(self.data) for k in range(l // self.B, len(self.max_buckets)): nl = k * self.B nr = (k+1) * self.B if r <= nl: break if l <= nl and nr <= r: self.add_buckets[k] += x self.max_buckets[k] += x else: start = max(l, nl) stop = min(r, nr, len(self.data)) for i in range(start, stop): self.data[i] += x # バケットの最大値の更新 self.max_buckets[k] = -INF for i in range(nl, min(nr, len(self.data))): s = self.add_buckets[k] + self.data[i] self.max_buckets[k] = max(self.max_buckets[k], s) def range_max(self, l: int, r: int) -> int: """[l, r) の最大値""" assert 0 <= l < r <= len(self.data) res = -INF for k in range(l // self.B, len(self.max_buckets)): nl = k * self.B nr = (k+1) * self.B if r <= nl: break if l <= nl and nr <= r: res = max(res, self.max_buckets[k]) else: start = max(l, nl) stop = min(r, nr, len(self.data)) for i in range(start, stop): res = max(res, self.add_buckets[k] + self.data[i]) return res def shakutori(a: list, factory): n = len(a) state = factory() hi = -1 for lo in range(n): if lo > hi: hi = lo - 1 state = factory() # できるだけ伸ばす while hi+1 < n and state.can_expand(a[hi+1]): state.expand(a[hi+1]) hi += 1 if lo <= hi: yield state, lo, hi state.shrink(a[lo]) class WindowState: def __init__(self): self.sd = RangeAddRangeMax([0] * N) self.q = deque() def can_expand(self, v) -> bool: if len(self.q) == 0: return True x, _, _ = v return x - self.q[0][0] <= A def expand(self, v): self.q.append(v) _, y, val = v cnt, l, r = find_interval(ys, y-A, y) if cnt > 0: self.sd.range_add(l, r+1, val) def shrink(self, v): assert len(self.q) > 0 assert self.q[0] == v self.q.popleft() _, y, val = v cnt, l, r = find_interval(ys, y-A, y) if cnt > 0: self.sd.range_add(l, r+1, -val) INF = 1 << 62 N, A = map(int, input().split()) ps = [] for _ in range(N): X, Y, V = map(int, input().split()) ps.append((X, Y, V)) ps.sort() # X 座標 : しゃくとり法で点を集める # Y 座標 : 区間Add区間Maxで最大値を求める # Y 座標の全ての点を昇順で持ち、インデックス計算できるようにする ys = sorted(set(y for _, y, _ in ps)) ans = 0 for st, _, _ in shakutori(ps, WindowState): res = st.sd.range_max(0, N) ans = max(ans, res) print(ans)