The Time Traveler's Paradox | Coding Challenges

Description

Medium

The Time Traveler's Paradox

A time traveler must visit historical events without causing paradoxes. Each event has a start time, end time, and importance value.

The traveler cannot attend overlapping events (events that share any time in common). However, events that share only an endpoint (one ends exactly when another starts) do NOT overlap.

Find the maximum total importance the traveler can achieve by selecting non-overlapping events.

Note: This is similar to the weighted job scheduling problem.

Input Format

The first line contains an integer n, the number of events. The next n lines each contain three integers: start, end, and importance.

Output Format

Print a single integer representing the maximum total importance achievable.

Examples

Example 1

Input

4 1 3 50 2 5 20 4 6 70 6 8 60

Output

180

ExplanationSelect events [1,3] with importance 50, [4,6] with 70, and [6,8] with 60. Total = 180.

Example 2

Input

3 1 4 100 2 3 50 3 5 60

Output

160

ExplanationSelect [1,4] with 100 and [3,5]... wait, they overlap. Best is [2,3]+[3,5]=110 or [1,4]+[nothing]=100. Actually [2,3] ends at 3, [3,5] starts at 3, so they touch but don't overlap. So 50+60=110. Hmm, or just [1,4]=100. Best is 110.

Constraints

•

1 ≤ n ≤ 1000

•

1 ≤ start < end ≤ 10^6

•

1 ≤ importance ≤ 10^6

Code

Error

Case 1

Case 2

Input

4 1 3 50 2 5 20 4 6 70 6 8 60

Output

No output

Expected

180