Event Scheduling for Maximum Importance

Hong has a series of events each with a starting time, an ending time, and an importance score. Due to time conflicts, he can only attend events that do not overlap. Your task is to help him select a subset of these events in order to maximize the total importance score.

Formally, given \(n\) events where the \(i\)-th event has a start time \(s_i\), an end time \(e_i\), and an importance score \(w_i\), determine the maximum total importance score by selecting a subset of events such that no two selected events overlap (i.e. for any two selected events \(i\) and \(j\), either \(e_i \leq s_j\) or \(e_j \leq s_i\)).

This problem can be modeled as a weighted interval scheduling problem. A common recurrence for the optimal solution is:

[ dp[i] = \max( dp[i-1],, w_i + dp[\text{prev}(i)] ) ]

where \(\text{prev}(i)\) is the index of the rightmost event that does not conflict with event \(i\). Your solution should read input from stdin and output the result to stdout.

inputFormat

The input is given via standard input and is formatted as follows:

• The first line contains an integer \(n\) representing the number of events.
• The next \(n\) lines each contain three integers \(s_i\), \(e_i\), and \(w_i\) separated by spaces, representing the start time, end time, and importance score of the \(i\)-th event respectively.

For example:

5
1 3 9
2 5 6
4 6 7
6 8 4
5 7 5

outputFormat

The output, written to standard output, is a single integer which is the maximum total importance score that Hong can achieve by attending a subset of non-overlapping events.

## sample

5
1 3 9
2 5 6
4 6 7
6 8 4
5 7 5

20

</p>