Informatica Online Judge

  휴대폰 스트랩 [0993 / 03E1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 26   Total Tried : 408


The Champion of this Problem (C++) : gs16051 - ms / 604byte
My Best Submission (C++) : N/A

[JOI 2014 Spring Camp]

Background

스트랩이란 휴대폰에 달 수 있는 장식 줄을 말한다.

요즘 나오는 스트랩은 스트랩끼리 연결해서 달 수 있는 제품이 있다.

경곽이는 이번에 휴대폰을 하나 장만했다. 그리고 맘에 드는 스트랩을 달려고 한다.

스트랩는 모두 N개가 있으며, 각 스트랩 마다 경곽이의 만족도가 주어진다.

그리고 각 스트랩은 그 스트랩에 몇 개의 스트랩을 더 연결할 수 있는지의 정보도 주어진다.

N개의 스트랩과 그 스트랩에 대한 만족도와 연결가능한 수 가 주어질 때, 경곽이의 만족도를 최대로 할 수 있는 방법을 알고리즘으로 설계하시오.

Input

첫 번째 줄에 스트랩의 수 N이 주어진다.

둘째 줄부터 N줄에 걸쳐서 각 스트랩의 연결가능 수와 만족도가 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= N <= 2,000
0 <= 연결가능 수 <= N
-1,000,000 <= 만족도 <= 1,000,000

Output

주어진 조건에서 최대 만족도를 출력한다. 단, 모두 마음에 들지 않으면 안 달아도 된다.

IO Example

입력
5
0 4
2 -2
1 -1
0 1
0 3

출력
5

* 설명 : 스트랩 2를 휴대전화에 직접 연결하고, 스트랩 1과 5를 각각 2에 연결하면 만족도가 5가 되고 더 이상 좋은 만족도를 얻을 수는 없다.

입력2
6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

출력2
0

* 설명 : 어떻게 달더라도 만족하지 못한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]