## https://yukicoder.me/problems/no/3214 from collections import deque MIN_VALUE = -10 ** 18 class LazySegmentTree: """ 非再帰版遅延セグメント木。 更新は「加法」、取得は「最大値」のもの限定。 取得のところの都合で取得演算子は可換になっている必要がある。 """ def __init__(self, init_array): n = 1 while n < len(init_array): n *= 2 self.size = n self.array = [MIN_VALUE] * (2 * self.size) self.lazy_array = [0 for _ in range(2 * self.size)] for i, a in enumerate(init_array): self.array[self.size + i] = a end_index = self.size start_index = end_index // 2 while start_index >= 1: for i in range(start_index, end_index): self.array[i] = max(self.array[2 * i], self.array[2 * i + 1]) end_index = start_index start_index = end_index // 2 def _propagates(self, *ids): for i in reversed(ids): self._propagate(i) def _propagate(self, i): v = self.lazy_array[i] if v == 0: return if i < self.size: self.lazy_array[2 * i] += v self.lazy_array[2 * i + 1] += v self.array[2 * i] += v self.array[2 * i + 1] += v self.lazy_array[i] = 0 def _get_target_index(self, l, r): L = l + self.size; R = r + self.size lm = (L // (L & -L)) >> 1 rm = (R // (R & -R)) >> 1 while 0 < L and L < R: if R <= rm: yield R if L <= lm: yield L L >>= 1; R >>= 1 while L > 0: yield L L >>= 1 def add(self, l, r, x): # 2. 区間[l, r)のdata, lazyの値を更新 L = self.size + l; R = self.size + r *ids, = self._get_target_index(l, r) self._propagates(*ids) while L < R: if R & 1: R -= 1 self.lazy_array[R] += x self.array[R] += x if L & 1: self.lazy_array[L] += x self.array[L] += x L += 1 L >>= 1; R >>= 1 # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する for i in ids: if i < self.size: self.array[i] = max(self.array[2 * i], self.array[2 * i + 1]) def get_max(self, l, r): # 1. トップダウンにlazyの値を伝搬 self._propagates(*self._get_target_index(l, r)) L = self.size + l; R = self.size + r # 2. 区間[l, r)の最大値を求める s = MIN_VALUE while L < R: if R & 1: R -= 1 s = max(s, self.array[R]) if L & 1: s = max(s, self.array[L]) L += 1 L >>= 1; R >>= 1 return s def main(): N, A = map(int, input().split()) xyv = [] for _ in range(N): x, y, v = map(int, input().split()) xyv.append((2 * x, 2 * y, v)) # Y座標について座標圧縮 y_set = set() for _, y, _ in xyv: y_set.add(y) y_set.add(y + 2 * A) y_set.add(y + 1) y_set.add(y + 2 * A + 1) y_set.add(y - 1) y_set.add(y + 2 * A - 1) y_list = list(y_set) y_list.sort() y_map = {} for i, y in enumerate(y_list): y_map[y] = i y_max = len(y_list) layz_seg_tree = LazySegmentTree([0] * y_max) x_map = {} x_keys = set() for x, y, v in xyv: if x not in x_map: x_map[x] = [] x_map[x].append((y, v)) x_keys.add(x + 1) x_keys.add(x) x_keys.add(x - 1) x_keys.add(x + 2 * A + 1) x_keys.add(x + 2 * A) x_keys.add(x + 2 * A - 1) x_list = list(x_keys) x_list.sort() queue = deque() answer = 0 for x in x_list: while len(queue) > 0 and queue[0][0] < (x - 2 * A): _, old_y_array = queue.popleft() for y, v in old_y_array: y_ = y_map[y] y1 = y_map[y + 2 * A] layz_seg_tree.add(y_, y1 + 1, -v) if x in x_map: y_array = x_map[x] for y, v in y_array: y_ = y_map[y] y2 = y_map[y + 2 * A] layz_seg_tree.add(y_, y2 + 1, v) queue.append((x, y_array)) ans = layz_seg_tree.get_max(0, layz_seg_tree.size) answer = max(ans, answer) print(answer) if __name__ == "__main__": main()