from itertools import accumulate from math import inf import sys from math import inf from typing import Callable, Generic, Sequence, TypeVar ElmType = TypeVar("ElmType") class SegmentTree(Generic[ElmType]): def __init__(self, seq: Sequence[ElmType], op: Callable[[ ElmType, ElmType], ElmType], init: ElmType) -> None: self._size = 1 << ((len(seq) - 1).bit_length()) self.data = [init] * (2 * self._size) self.data[self._size:self._size + len(seq)] = seq self._op = op self._init = init for i in reversed(range(1, self._size)): self._update(i) def _update(self, k: int): self.data[k] = self._op(self.data[k * 2], self.data[k * 2 + 1]) def set(self, idx: int, x: int): idx += self._size self.data[idx] = x idx //= 2 while idx > 0: self._update(idx) idx //= 2 def prod(self, l_idx: int, r_idx: int) -> ElmType: l_idx += self._size r_idx += self._size left_result = self._init right_result = self._init while l_idx < r_idx: if l_idx % 2: left_result = self._op(left_result, self.data[l_idx]) l_idx += 1 if r_idx % 2: r_idx -= 1 right_result = self._op(self.data[r_idx], right_result) l_idx //= 2 r_idx //= 2 return self._op(left_result, right_result) def all_prod(self) -> ElmType: return self.data[1] def get(self, idx: int) -> ElmType: return self.data[idx + self._size] def printe(*args, end="\n", **kwargs): print(*args, end=end, file=sys.stderr, **kwargs) def main(): N, W, D = map(int, input().split()) stones = [list(map(int, input().split())) for _ in range(N)] type_0_dp_table = [[-inf for _ in range(W + 1)] for _ in range(N + 1)] type_1_dp_table = [[-inf for _ in range(W + 1)] for _ in range(N + 1)] type_0_dp_table[0][0] = 0 type_1_dp_table[0][0] = 0 for idx in range(N): for c_w in range(W + 1): type_0_dp_table[idx + 1][c_w] = max( type_0_dp_table[idx + 1][c_w], type_0_dp_table[idx][c_w] ) type_1_dp_table[idx + 1][c_w] = max( type_1_dp_table[idx + 1][c_w], type_1_dp_table[idx][c_w] ) if c_w + stones[idx][1] <= W: if stones[idx][0] == 0: type_0_dp_table[idx + 1][c_w + stones[idx][1]] = max( type_0_dp_table[idx + 1][c_w + stones[idx][1]], type_0_dp_table[idx][c_w] + stones[idx][2] ) else: type_1_dp_table[idx + 1][c_w + stones[idx][1]] = max( type_1_dp_table[idx + 1][c_w + stones[idx][1]], type_1_dp_table[idx][c_w] + stones[idx][2] ) last_type_0 = type_0_dp_table[-1] last_type_1 = type_1_dp_table[-1] last_type_1_accum_max = SegmentTree(last_type_1, max, -inf) max_value = 0 for type_0_w in range(W + 1): max_value = max(max_value, last_type_0[type_0_w] + last_type_1_accum_max.prod( max(type_0_w - D, 0), min(type_0_w + D, W - type_0_w) + 1)) print(max_value) if __name__ == "__main__": main()