JOI Spring Camp 2014 Day- 열쇠고리 > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


4822 : 열쇠고리

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
7 회   
시도횟수
45 회   

문제

상현이는 열쇠고리를 N개 가지고있다. 

열쇠고리는 1에서 N까지의 번호가 매겨져있다. 상현이는 열쇠고리 중 일부를 스마트폰​에 장착하고 싶어한다.

 

상현이가 가지고있는 열쇠고리는 다른 열쇠고리를 장착 할 수있는 구멍이 몇개 붙어있다. 

각각의 열쇠고리는 스마트폰​에 직접 장착하거나 다른 열쇠고리의 구멍에 장착할 수 있다. 

 

스마트폰​에 존재하는 구멍은 1개뿐이다.

 

열쇠고리에 장착했을 때 얻을 수있는 만족도가 정해져있다. 이 만족도는 하나의 정수로 표현된다. 

일부 열쇠고리는 상현이가 싫어하는 경우가 있는데, 이 경우 만족도는 음수가 된다.

 

상현이는 스마트폰에 연결되어있는 열쇠고리들의 만족도 총합을 최대로 하고 싶다. 

 

모든 구멍에 열쇠고리가 장착되어 있지 않아도 되고, 열쇠고리를 한개도 장착하지 않아도 된다.

 

상현이가 가지고있는 N개의 열쇠고리 정보가 주어진다. 

열쇠고리를 적절히 장착하여 만족도 총합의 최대 값을 구하는 프로그램을 작성하라.​​

 


입력형식

첫 번째 줄에는 정수 N이 주어진다. N은 열쇠고리의 개수를 나타낸다.

그 다음, N개의 행 중 i 번째 줄 (1 ≤ i ≤ N)에는 정수 A​i , B​i 가 공백을 구분으로 주어진다.

i번 열쇠고리는 는 구멍이 A​i개 있고 그 열쇠고리를 장착했을 때 만족도가 B​i임을 의미한다.​

 

​1 ≤ N ≤ 2 000

0 ≤ A​i ≤ N (1 ≤ i ≤ N)

−1 000 000 ≤ B​i ≤ 1 000 000 (1 ≤ i ≤ N) 


출력형식

스마트폰에 연결되어있는 열쇠고리의 만족도 총합의 최대값을 출력한다. 


입력 예

복사하기

5
0 4
2 -2
1 -1
0 1
0 3

출력 예

복사하기

5

입력 예

복사하기

6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

출력 예

복사하기

0


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP