외주 - 구름LEVEL
외주
Quiz Info
외주
100points
Participant
42
Solved Rate
38%
3
4


형기는 뛰어난 개발 실력을 가지고 있지만 게을러서 아직 일자리를 구하지 못했다. 사실 집에서 뒹굴거리는 게 더 좋아서 구할 생각도 없는 듯하다. 그러던 어느 날, 형기는 슬슬 새 컴퓨터를 장만해야겠다고 생각이 들었고 그러려면 돈이 필요하다는 것을 깨달았다. 어쩔 수 없이 형기는 외주작업을 맡아 함으로써 돈을 벌고자 한다. 형기는 외주 전문 사이트에 글을 올린 후, 그대로 잠이 들었다.

다음 날 일어나서 자신이 올린 글을 확인해보니 수많은 외주작업 요청이 들어온 것을 보고는 입이 쩍 벌어졌다. 벌써부터 돈이 굴러들어오는 생각에 입꼬리가 올라갔지만, 각 외주작업의 요청에는 계약금과 마감기한이 정해져 있어 신중하게 골라야만 했다. 아무리 형기의 개발 실력이 뛰어나도 이 수많은 외주작업을 해내기엔 벅찬 일이었기 때문이다.

자세한 상황은 다음과 같다. 형기에게 들어온 외주작업 요청의 수는 N개이다. 각 외주작업은 계약금 와 마감기한 를 가지고 있다. 형기는 어떤 외주작업이든지 끝마치는 데 하루가 소요된다. 이러한 상황에서 형기는 최대한 많은 돈을 벌 수 있도록 외주작업을 선택하고자 한다. 형기가 벌 수 있는 최대 금액은 얼마일까?


입력


첫째 줄에 형기에게 들어온 외주작업 요청의 수를 나타내는 정수 N이 주어진다. (단, )

이후 N개의 줄에 걸쳐서 각 줄마다 두 개의 정수 가 공백으로 구분되어 주어진다. 는 i번째 외주작업을 완료했을 때 받는 금액, 는 i번째 외주작업의 데드라인이다. (단, )

또한, 현 시점을 1일째로 기준을 잡는다. 즉, 오늘이 지나고 나면 데드라인이 1인 외주작업을 더 이상 완료할 수 없다.


출력


형기가 벌 수 있는 최대의 금액을 출력한다.



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
5
1002
191
272
251
153
Output
142
Example 2
Input
7
11
21
31
41
51
61
71
Output
7
Example 3
Input
10
4510
299
98
457
186
255
404
233
402
361
Output
310
Example 4
Input
15
821
4611
9510
159
311
38
535
1911
1912
936
6314
464
687
797
554
Output
733
⋇ Please keep the input and output formats carefully
Q & A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다.
다른 수강생들과 질문과 답변을 주고 받으며 함께 성장하세요!

Registered Questions (0)