import bisect class SegmentTreeMax: def __init__(self, size): self.n = 1 while self.n < size: self.n <<= 1 self.size = self.n self.tree = [0] * (2 * self.n) def update(self, idx, value): idx += self.n if self.tree[idx] >= value: return self.tree[idx] = value while idx > 1: idx >>= 1 new_val = max(self.tree[2*idx], self.tree[2*idx+1]) if self.tree[idx] == new_val: break self.tree[idx] = new_val def query(self, l, r): res = 0 l += self.n r += self.n while l < r: if l % 2 == 1: res = max(res, self.tree[l]) l += 1 if r % 2 == 1: r -= 1 res = max(res, self.tree[r]) l >>= 1 r >>= 1 return res # Read input n = int(input()) cakes = [] all_B = [] for _ in range(n): A, B, C = map(int, input().split()) cakes.append( (A, B, C) ) all_B.append(B) # Compress B coordinates sorted_B = sorted(list(set(all_B))) m = len(sorted_B) # Sort cakes by A descending then B descending cakes.sort(key=lambda x: (-x[0], -x[1])) # Group by A groups = [] current_A = None current_group = [] for cake in cakes: A = cake[0] if A != current_A: if current_group: groups.append(current_group) current_group = [cake] current_A = A else: current_group.append(cake) groups.append(current_group) # Initialize segment tree st = SegmentTreeMax(m) max_answer = 0 for group in groups: dps = [] for cake in group: A_j, B_j, C_j = cake # Compute q_idx = bisect_right(B_j) q_idx = bisect.bisect_right(sorted_B, B_j) # Query from q_idx to m max_prev = st.query(q_idx, m) current_dp = C_j + (max_prev if max_prev > 0 else 0) dps.append(current_dp) if current_dp > max_answer: max_answer = current_dp # Update the segment tree for each cake in the group for cake, current_dp in zip(group, dps): B_j = cake[1] # Find the compressed index b_idx = bisect.bisect_left(sorted_B, B_j) # Update the segment tree at b_idx with current_dp st.update(b_idx, current_dp) print(max_answer)