5338 : B39 - 타로의 아르바이트
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
타로는 오늘부터 $ D $ 일 동안 일을 하려고 합니다.
일의 선택지는 $ N $ 개가 있으며, $ i $ 번째 일은 $ X_i $ 일째 이후부터 선택할 수 있고, 완료하면 $ Y_i $ 원을 받습니다.
일을 하나 완료하는 데 $ 1 $ 일이 걸릴 때, 타로가 벌 수 있는 최대 금액은 얼마입니까?
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le D \le 2000$
• $1 \le X_i \le D$
• $1 \le Y_i \le 10^6$
• 입력되는 모든 값은 정수입니다.
일의 선택지는 $ N $ 개가 있으며, $ i $ 번째 일은 $ X_i $ 일째 이후부터 선택할 수 있고, 완료하면 $ Y_i $ 원을 받습니다.
일을 하나 완료하는 데 $ 1 $ 일이 걸릴 때, 타로가 벌 수 있는 최대 금액은 얼마입니까?
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le D \le 2000$
• $1 \le X_i \le D$
• $1 \le Y_i \le 10^6$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $ N, D $ 가 주어집니다.
이후 $ N $ 개의 줄에 각 일의 정보 $ X_i, Y_i $ 가 주어집니다.
이후 $ N $ 개의 줄에 각 일의 정보 $ X_i, Y_i $ 가 주어집니다.
출력 설명
타로가 벌 수 있는 최대 금액을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 1
2 4
2 3
3 4
4 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
12도움
$ 1, 2, 4, 3 $ 번째 순서로 일을 하면 $ 1+4+4+3=12 $ 원을 얻을 수 있으며, 이것이 최대입니다.