Maximum Happiness

You are given a list of events where each event is represented by a start time, an end time, and a happiness value. Your task is to choose a subset of non-overlapping events such that the total happiness is maximized. Note that you can attend as many events as you want as long as their time intervals do not overlap.

Formally, you are given events \( (s_i, e_i, h_i) \) for \( i = 1, 2, \dots, n \). Select a subset \( S \) of events such that for any two events \( (s_i, e_i, h_i) \) and \( (s_j, e_j, h_j) \) in \( S \), the intervals do not overlap (i.e. \( e_i \le s_j \) or \( e_j \le s_i \)). The goal is to maximize the sum \( \sum_{(s,e,h) \in S} h \).

inputFormat

The input consists of several test cases. For each test case, the first line contains a single integer \( n \) indicating the number of events. Each of the next \( n \) lines contains three integers: the start time, the end time, and the happiness value of an event. The input terminates when a test case with \( n = 0 \) is encountered. This test case should not be processed.

outputFormat

For each test case, output a single line containing the maximum total happiness that can be achieved by attending non-overlapping events.

3
60 120 100
180 240 200
150 210 150
3
120 180 50
180 240 100
300 360 150
0

300
300