Maximum Revenue from Non-Overlapping Parking Meters

You are given m parking meters. Each parking meter is represented by an interval [s, e) along with a revenue r. The interval [s, e) indicates that the meter is active starting from time s up to (but not including) time e. Two meters are considered overlapping if their intervals intersect.

Your task is to select a subset of non-overlapping parking meters so that the total revenue is maximized. This problem can be solved by a dynamic programming approach similar to the weighted interval scheduling problem. The recurrence can be written in \(\LaTeX\) as:

\[dp[i] = \max(dp[i-1], r_i + dp[j])\]

Here, \(dp[i]\) is the maximum revenue using the first \(i\) intervals (after sorting by end time), \(r_i\) is the revenue for the \(i\)th interval, and \(j\) is the largest index less than \(i\) that does not conflict with the \(i\)th interval (i.e. \(e_j \leq s_i\)).

inputFormat

The input is read from stdin and has the following format:

M
s1 e1 r1
s2 e2 r2
... 
sM eM rM

Where:

• M is the number of parking meters.
• Each of the next M lines contains three integers: the start time s, the end time e, and the revenue r, separated by spaces.

All numbers are integers.

outputFormat

The output is a single integer written to stdout representing the maximum total revenue that can be obtained by selecting a subset of non-overlapping parking meters.

## sample

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

22