회의실 시연 예약의 마감

문제

한 업무 공간은 회의실 한 곳을 제품 시연 행사에 빌려주려고 한다. 운영 기간에는 길이가 같은 시간 칸이 N개 있으며, 이른 순서대로 1번부터 N번까지 번호가 붙어 있다. 운영자는 N개의 예약 요청을 받았다. 각 요청은 회의실을 정확히 한 시간 칸 동안 사용하며, 요청을 수락하여 시연을 진행하면 정해진 이용료를 받는다. 요청을 거절하면 이용료를 받지 않고 별도의 비용도 발생하지 않는다. 각 요청에는 시연을 끝내야 하는 마감 칸이 지정되어 있다. 마감 칸이 d인 요청은 1번부터 d번까지의 시간 칸 중 어느 하나에 배정할 수 있다. 요청자가 지정한 시작 칸은 없으므로, 이 범위 안에서는 운영자가 자유롭게 시간을 정할 수 있다. 한 요청을 두 칸 이상에 배정하거나 여러 요청을 같은 칸에 배정할 수 없다. 마감 칸을 지난 뒤에는 빈 칸이 남더라도 해당 요청을 진행할 수 없다. 모든 요청의 준비와 정리 시간은 이용 시간에 포함되어 있다. 따라서 서로 연속한 시간 칸에 다른 요청을 배정해도 추가 간격은 필요하지 않다. 요청마다 이용료가 다를 수 있지만, 같은 요청의 이용료는 어느 허용 칸에 배정하더라도 변하지 않는다. 요청끼리의 선후 관계나 함께 수락해야 하는 조건도 없다. 운영자는 가능한 요청들을 골라 적절한 시간 칸에 배정하여 이용료 합을 최대화하려고 한다. 입력에는 각 요청의 마감 칸과 이용료가 주어진다. 모든 요청을 수락할 수 없을 수도 있으며, 일부 시간 칸을 비워 두어도 된다. 어떤 요청을 선택했는지나 실제 배정표를 출력할 필요는 없고, 얻을 수 있는 이용료 합의 최댓값만 구한다. 최대 합을 만드는 선택이나 배정이 여러 개라면 어느 것을 기준으로 삼아도 출력할 값은 같다. 요청을 하나도 수락하지 않은 경우의 이용료 합은 0으로 정의한다.

입력

첫째 줄에 정수 N이 주어진다. 1≤N≤15,000이다.
다음 N개 줄에 각 요청의 마감 칸 d와 이용료 w가 주어진다. d,w는 정수이며 1≤d≤N, 0≤w≤1,000,000,000이다. 요청은 임의의 순서로 주어지며, 마감 칸과 이용료가 모두 같은 요청도 서로 다른 요청이다.

출력

얻을 수 있는 이용료 합의 최댓값을 정수로 한 줄에 출력한다. 모든 요청의 이용료가 0이면 0을 출력한다. 답은 부호 있는 64비트 정수 범위에 들어간다.

5
1 40
2 70
2 60
4 30
1 90

190

3
1 8
1 8
1 2

8

1
1 0

0

출처: Devin.KR 자체 제작