This page is still under construction.

Parts of this page are still being built. What you see may change.

Meeting Room Scheduling 3

Interview

Time limit1sMemory limit256 MB

Summary
Choose non-overlapping meetings, where each meeting's time overlaps only its immediate neighbors in the input order, to maximize the total attendee count.
Level

Medium6 of 10

Topics
Dynamic programming, Greedy, Intervals, Array
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 an attendee count, and no two meetings may take place in the meeting room at the same time. Once a meeting starts, it cannot be interrupted, and a meeting may start at the exact moment another meeting ends. A meeting's start time is always less than its end time. Find the maximum total number of attendees that can attend 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 attendee count of each meeting are given, separated by spaces.

Output

Print the maximum total number of attendees that can attend meetings in the meeting room on the first line.

Constraints

  • 1 ≤ N ≤ 100,000
  • For any meeting K (1 ≤ K ≤ N), its time overlaps with meeting K − 1 and meeting K + 1, and does not overlap with any other meeting.
  • The start time and end time of every meeting are natural numbers or 0, less than or equal to 231 − 1.
  • The start time and end time of every meeting are distinct.
  • The attendee count of a meeting is a natural number less than or equal to 1,000.

Examples1

  1. Example 1

    Input
    6
10 40 80
30 60 60
50 80 70
70 100 100
90 120 40
110 140 50
    Expected output
    230