Meeting Room Scheduling 2

Interview

Time limit1sMemory limit256 MB

Summary

Given N meetings that overlap only with their immediate neighbors in the list, choose a non-overlapping subset maximizing total attendees.

Level: Medium6 of 10
Topics: Dynamic programming, Array, Intervals, Brute force
Solved: No attempts yet

Problem

Seojun received N meetings and one meeting room as a gift from his father. Each meeting has a start time, an end time, and a number of attendees, and no two meetings can take place in the meeting room at the same time. Once a meeting starts it cannot be interrupted, and the next meeting may start at the same moment the previous one ends. The start time of a meeting is always less than its end time. Find the maximum number of attendees that can take part in meetings when the N meetings are scheduled in the meeting room as efficiently as possible.

Input

The first line gives the number of meetings N. From the second line to the N + 1-th line, the start time, end time, and number of attendees of a meeting are given, separated by spaces.

Output

On the first line, print the maximum number of attendees that can take part in meetings in the meeting room.

Constraints

1 ≤ N ≤ 25
For any meeting K (1 ≤ K ≤ N), its meeting time overlaps with those of meetings K − 1 and K + 1, and does not overlap with those of any other meetings.
The start time and end time of every meeting are natural numbers or 0, less than or equal to $2^{31} - 1$ .
The start time and end time of every meeting are distinct from each other.
The number of attendees of a meeting is a natural number less than or equal to 1,000.

Examples1

Example 1

Input

Expected output