Under construction

Still being built. Things may change

Meeting Room Scheduling 4

Interview

Time limit1sMemory limit256 MB

Summary
Choose a set of non-overlapping meetings, where touching endpoints are allowed, to maximize the total number of attendees.
Level

Medium5 of 10

Topics
Dynamic programming, Sorting, Binary search, Intervals
Solved
No attempts yet

Problem

Seojun received N meetings and one meeting room as a gift from his father. Each meeting is given by its start time, end time, and the number of people attending, and two or more meetings cannot take place in the meeting room at the same time. Once a meeting starts, it cannot be interrupted, and a meeting can 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 people 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 number of people of each meeting are given, separated by spaces.

Output

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

Constraints

  • 1 ≤ N ≤ 100,000
  • The time intervals of any two of the N meetings can overlap.
  • 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 different from each other.
  • The number of people of every meeting is a natural number less than or equal to 1,000.

Examples2

  1. Example 1

    Input
    5
10 50 50
30 60 60
20 120 100
80 100 50
110 140 70
    Expected output
    180

  2. Example 2

    Input
    5
10 20 50
30 60 60
25 70 100
80 90 50
11 100 70
    Expected output
    200