from collections import defaultdict from heapq import heappush, heappop from typing import Iterable class DeletableHeapq: def __init__(self, items: Iterable=[], reverse=False) -> None: self._heap = [] self._sum = 0 self._len = len(list(items)) self._count = defaultdict(int) self._sign = -1 if reverse else 1 for x in items: self.push(x) def __len__(self) -> int: return self._len def __contains__(self, x: int) -> bool: return self._count.get(x, 0) > 0 def push(self, x: int) -> None: self._sum += x self._len += 1 self._count[x] += 1 heappush(self._heap, x * self._sign) def pop(self) -> int: assert self._len > 0 self._update() x = heappop(self._heap) * self._sign self._sum -= x self._len -= 1 self._count[x] -= 1 return x def top(self) -> int: assert len(self) > 0 self._update() return self._heap[0] * self._sign def remove(self, x: int) -> None: assert x in self self._sum -= x self._len -= 1 self._count[x] -= 1 def _update(self) -> None: while self._heap: x = self._heap[0] * self._sign if x in self: return heappop(self._heap) @property def sum(self) -> int: return self._sum def count(self, x: int) -> int: return self._count.get(x, 0) N, T = map(int, input().split()) SIZE = 2 << 17 LP = [[] for _ in range(SIZE)] RP = [[] for _ in range(SIZE)] for _ in range(N): l, r, p = map(int, input().split()) LP[l].append(p) RP[r].append(p) dp = [0] * SIZE dhq = DeletableHeapq([0], reverse=True) for i, (lp, rp) in enumerate(zip(LP, RP)): for p in lp: dhq.push(p) dp[i] = max(dp[i - 1], dp[i - T] + dhq.top()) for p in rp: dhq.remove(p) print(dp[-1])