Dự án

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Bạn có $N$ dự án cần được hoàn thành (không nhất thiết phải hoàn thành hết tất cả). Dự án thứ $i$ bắt đầu vào ngày thứ $a_{i}$ , kết thúc vào ngày thứ $b_{i}$ và bạn sẽ được trả công là $p_{i}$ . Mỗi ngày bạn chỉ được làm tối đa một dự án duy nhất.

Yêu cầu: Tìm số tiền tối đa bạn có thể kiếm được.

Dữ liệu vào

Dòng đầu tiên gồm số nguyên dương $N$ ( $1 \leq N \leq 100 000$ ).
$N$ dòng tiếp theo, mỗi dòng gồm $3$ số nguyên dương $a_{i}, b_{i}, p_{i}$ ( $a_{i}, b_{i}, p_{i} \leq 1 000 000$ ).

Dữ liệu ra

Một số nguyên dương duy nhất là số tiền tối đa bạn có thể kiếm được.

Ví dụ

Input	Output	Giải thích
4 2 4 4 3 6 6 6 8 2 5 7 3	7	Chọn dự án $1$ (ngày $2$ – $4$ , trả công $4$ ) và dự án $4$ (ngày $5$ – $7$ , trả công $3$ ). Tổng tiền $= 4 + 3 = 7$ . Không có cách chọn nào cho tổng lớn hơn.

Bình luận

Không có bình luận tại thời điểm này.