Lịch học (Class Schedule)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Trong một ngày, nhà trường nhận được $N$ đề xuất sử dụng cùng một phòng máy.

Đề xuất thứ $i$ cần sử dụng phòng máy liên tục từ thời điểm $S_i$ đến thời điểm $T_i$. Nếu đề xuất này được tổ chức, nhà trường nhận được $V_i$ điểm hiệu quả.

Do chỉ có một phòng máy, các buổi học được chọn không được chồng lấn thời gian. Hai buổi học được xem là không chồng lấn nếu một buổi kết thúc không muộn hơn thời điểm buổi còn lại bắt đầu. Đặc biệt, nếu một buổi kết thúc đúng tại thời điểm một buổi khác bắt đầu thì hai buổi đó có thể cùng được chọn.

Hãy chọn một số buổi học sao cho không có hai buổi được chọn chồng lấn thời gian và tổng điểm hiệu quả của các buổi được chọn là lớn nhất.

Input

• Dòng đầu chứa số nguyên $N$ — số đề xuất sử dụng phòng máy.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $S_i$, $T_i$, $V_i$, lần lượt là thời điểm bắt đầu, thời điểm kết thúc và điểm hiệu quả của đề xuất thứ $i$.

Output

In ra một số nguyên duy nhất — tổng điểm hiệu quả lớn nhất có thể đạt được.

Subtask

Trong tất cả các Subtask: $1 \le S_i < T_i \le 10^9$; $1 \le V_i \le 10^9$.

• Subtask 1: $1 \le N \le 20$.
• Subtask 2: $1 \le N \le 3000$.
• Subtask 3: $1 \le N \le 2\cdot10^5$.

Ví dụ

Ví dụ 1

Input

5
1 3 5
2 5 6
4 6 5
6 7 4
5 8 11

Output

17

Giải thích

Có thể chọn buổi học từ thời điểm $2$ đến $5$, nhận được $6$ điểm, và buổi học từ thời điểm $5$ đến $8$, nhận được $11$ điểm.

Hai buổi này chỉ tiếp giáp tại thời điểm $5$: buổi thứ nhất kết thúc đúng lúc buổi thứ hai bắt đầu nên chúng không chồng lấn.

Tổng điểm hiệu quả nhận được là

Ví dụ 2

Input

4
1 2 4
2 3 4
3 4 4
1 4 13

Output

13

Giải thích

Nếu chọn ba buổi học $[1,2]$, $[2,3]$ và $[3,4]$ thì tổng điểm hiệu quả là

Trong khi đó, chỉ cần chọn buổi học $[1,4]$ đã nhận được $13$ điểm.

Vì $13>12$, tổng điểm hiệu quả lớn nhất là $13$.

Ví dụ 3

Input

3
1 10 5
2 3 4
3 4 4

Output

8

Giải thích

Có thể chọn hai buổi học $[2,3]$ và $[3,4]$. Hai buổi này không chồng lấn vì buổi thứ nhất kết thúc đúng tại thời điểm buổi thứ hai bắt đầu.

Tổng điểm hiệu quả là

Buổi học $[1,10]$ có $5$ điểm nhưng chồng lấn với cả hai buổi trên, nên không thể tạo ra tổng điểm lớn hơn.