Lịch ôn tập (Study Schedule)

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

Đề bài

Trong một ngày, phòng máy của đội tuyển có $N$ đề xuất sử dụng. Đề xuất thứ $i$ 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 chọn.

Do chỉ có một phòng máy, hai đề xuất được chọn không được chồng lấn thời gian. Nếu một đề xuất kết thúc đúng tại thời điểm đề xuất khác bắt đầu thì hai đề xuất đó vẫn có thể cùng được chọn.

Hãy chọn một số đề xuất sao cho tổng điểm hiệu quả là lớn nhất.

Input

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

Với mọi $i$: $0 \le S_i < T_i \le 10^9$ và $1 \le V_i \le 10^9$.

Output

In 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$.
• Subtask 2 (30%): $1 \le N \le 2000$.
• Subtask 3 (40%): $1 \le N \le 2\cdot 10^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

Chọn đề xuất $[2,5]$ có giá trị $6$ và đề xuất $[5,8]$ có giá trị $11$. Hai khoảng chỉ tiếp xúc tại thời điểm $5$ nên hợp lệ; tổng là $17$.

Ví dụ 2

Input

4
1 2 4
2 4 5
1 4 10
4 6 3

Output

13

Giải thích

Chọn $[1,4]$ có giá trị $10$ và $[4,6]$ có giá trị $3$. Tổng đạt $13$.

Ví dụ 3

Input

3
1 10 7
2 3 4
3 4 4

Output

8

Giải thích

Hai đề xuất $[2,3]$ và $[3,4]$ không chồng lấn, cho tổng $8$, lớn hơn việc chọn riêng $[1,10]$ có giá trị $7$.