33068번 - Savvy Seller 서브태스크다국어

문제

Hanbyeol is a seasoned sales representative. She has $N$ meeting opportunities with various companies and wants to select some of these meetings to attend. In her early career as a junior saleswoman, she aimed to attend as many meetings as possible. However, now, as a veteran, she knows which meetings are more important and which are less critical.

Hanbyeol knows the start and end times for each meeting and the expected profit she can earn by attending. If two meetings overlap in time, she cannot attend both. It is implied that meetings are considered overlapping only if one meeting's end time exceeds the next meeting's start time; meetings, where the end time of one equals the start time of the next, are allowed.

Write a program to help Hanbyeol create a meeting schedule that maximizes her total expected profit.

입력

The first line contains a single integer, $N,ドル denoting the meeting opportunities that Hanbyeol has. (1ドル \le N \le 100,000円$)

The $i$-th of the next $N$ lines contain three space-separated integers: $s_i$ and $e_i,ドル denoting the starting and ending time of the $i$-th meeting, respectively, and $p_i,ドル denoting the expected profit Hanbyeol can earn by attending the $i$-th meeting. (0ドル \le s < e \le 10^9;$ 1ドル \le p \le 10^9$)

출력

Output the total profit when Hanbyeol schedules her meetings optimally.

제한

서브태스크 1 (40점)

Modified constraints apply: 1ドル \le N \le 10;$ 0ドル \le s < e \le 23$.

서브태스크 2 (40점)

Modified constraints apply: 1ドル \le N \le 100,000円;$ 0ドル \le s < e \le 10^9;$ $\boldsymbol{\underline{p_i=1}}$ for all 1ドル \le i \le N,ドル i.e, all meetings has the same expected profit.

서브태스크 3 (16점)

Modified constraints apply: 1ドル \le N \le 1,000円;$ 0ドル \le s < e \le 10^9$.

서브태스크 4 (4점)

Original constraints apply: 1ドル \le N \le 100,000円;$ 0ドル \le s < e \le 10^9$.

힌트