Bài toán: Tối đa hóa số tiền kiếm được từ các dự án

Đề bài

Bạn có ~ n ~ dự án mà bạn có thể tham gia. Mỗi dự án được mô tả bởi:

• Ngày bắt đầu ~ a_i ~,
• Ngày kết thúc ~ b_i ~,
• Số tiền thưởng ~ p_i ~.

Bạn chỉ có thể tham gia một dự án tại một thời điểm, nghĩa là thời gian tham gia các dự án không được trùng nhau. Nhiệm vụ của bạn là tối đa hóa tổng số tiền bạn có thể kiếm được.

Input

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng dự án.
• ~ n ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ a_i, b_i, p_i ~: ngày bắt đầu, ngày kết thúc và tiền thưởng của dự án.

Output

• In ra một số nguyên: tổng số tiền lớn nhất bạn có thể kiếm được.

Ràng buộc

• ~ 1 \leq n \leq 2 \cdot 10^5 ~
• ~ 1 \leq a_i \leq b_i \leq 10^9 ~
• ~ 1 \leq p_i \leq 10^9 ~

Ví dụ

Input:

4
2 4 4
3 6 6
6 8 2
5 7 3

Output:

7

Giải thích:

Bạn có thể chọn các dự án như sau:

• Tham gia dự án thứ nhất (~2 \to 4~) kiếm 4 tiền.
• Tham gia dự án thứ 4 (~5 \to 7~) kiếm thêm ~3~ tiền. Tổng cộng bạn kiếm được ~4 + 3 = 7~.