Xếp lịch công việc lợi nhuận tối đa

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Có $N$ công việc, mỗi công việc mất đúng $1$ đơn vị thời gian để hoàn thành. Công việc thứ $i$ có thời hạn $D_i$ (phải hoàn thành tại hoặc trước thời điểm $D_i$, tính từ thời điểm $1$) và mang lại lợi nhuận $P_i$. Tại mỗi đơn vị thời gian chỉ làm được tối đa một công việc. Hãy tìm tổng lợi nhuận lớn nhất có thể đạt được.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $D_i$ và $P_i$.

Dữ liệu ra

In ra tổng lợi nhuận lớn nhất.

Ví dụ
Input Output
4
4 20
1 10
1 40
1 30
60
Giới hạn
  • $1 \le N \le 10^5$.
  • $1 \le D_i \le N$, $1 \le P_i \le 10^9$.
Draft saved