Lịch học (Class Schedule)

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

Đề 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 liên tục từ thời điểm $S_i$ đến thời điểm $T_i$ và mang lại $V_i$ điểm hiệu quả nếu được tổ chức.

Do chỉ có một phòng máy, các đề xuất được chọn không được chồng lấn thời gian. Hai đề xuất được xem là không chồng lấn nếu một đề xuất kết thúc không muộn hơn thời điểm đề xuất còn lại bắt đầu. Vì vậy, 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ì cả hai vẫn có thể cùng được chọn.

Hãy chọn một số đề xuất sao cho không có hai đề xuất nào chồng lấn và tổng điểm hiệu quả là lớn nhất.

Input

• Dòng đầu chứa số nguyên dương $N$.
• Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên dương $S_i,T_i,V_i$ với $S_i<T_i$.

Output

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

Subtask

• Subtask 1 (30%): $1\le N\le 20$, $1\le S_i<T_i\le 10^9$, $1\le V_i\le 10^9$.
• Subtask 2 (30%): $1\le N\le 2000$, $1\le S_i<T_i\le 10^9$, $1\le V_i\le 10^9$.
• Subtask 3 (40%): $1\le N\le 2\times 10^5$, $1\le S_i<T_i\le 10^9$, $1\le V_i\le 10^9$.

Ví dụ

Ví dụ 1

Input

4
1 3 5
2 5 6
4 6 5
6 8 4

Output

14

Giải thích

Có thể chọn các đề xuất $(1,3,5)$, $(4,6,5)$ và $(6,8,4)$. Hai đề xuất cuối tiếp giáp tại thời điểm $6$ nên không chồng lấn. Tổng điểm là $14$.

Ví dụ 2

Input

5
1 2 10
2 3 10
3 4 10
1 4 25
4 5 5

Output

35

Giải thích

Chọn ba đề xuất đầu tiên và đề xuất cuối cùng được $10+10+10+5=35$, lớn hơn phương án chọn $(1,4,25)$ rồi $(4,5,5)$.

Ví dụ 3

Input

4
1 10 100
2 3 40
3 5 40
5 9 40

Output

120

Giải thích

Ba đề xuất $(2,3,40)$, $(3,5,40)$ và $(5,9,40)$ không chồng lấn và có tổng điểm $120$, lớn hơn $100$.