스트랩 Batch 컴파일 명령

승현이는 휴대전화에 부착하는 스트랩을 $N$개 가지고 있습니다. 스트랩에는 $1$ 이상 $N$ 이하의 정수 번호가 붙어 있습니다. 승현이는 이러한 스트랩들 중 일부를 본인의 휴대 전화에 달려고 합니다.

승현이가 가지고 있는 스트랩은 조금씩 달라서 어떤 스트랩들에는 다른 스트랩을 장착하기 위한 단자가 몇 개 붙어 있습니다. 각각의 스트랩은 휴대전화에 직접 부착하거나 다른 스트랩 단자에 장착할 수 있습니다. 휴대전화에 직접 부착할 수 있는 스트랩은 최대 1개입니다.

또한 각각의 스트랩에는 설치할 시 얻을 수 있는 행복도가 정해져 있습니다. 행복도는 하나의 정수로 표시됩니다. 승현이가 싫어하는 스트랩도 있고, 이 경우 행복도는 음수가 됩니다.

승현이는 휴대전화에 연결되어 있는 스트랩들의 행복도의 총 합을 최대화하고 싶습니다. 그러나 반드시 모든 단자에 스트랩이 붙어 있을 필요는 없고, 휴대전화에 스트랩을 장착하지 않아도 됩니다.

해야 할 일

승현이가 가지고 있는 $N$개의 스트랩의 정보가 주어집니다. 스트랩들을 적당히 연결하여 만들 수 있는 휴대전화에 연결된 스트랩들의 행복도의 총 합의 최댓값을 구하는 프로그램을 작성하세요.

입력

표준 입력에서 아래 데이터를 받습니다:

• 첫 번째 줄에 스트랩의 수 $N$이 주어집니다.
• $N$개 줄이 주어집니다. 이 중 $i$번째 줄 ($1 \le i \le N$)에는 두 개의 정수 $A_{i}$와 $B_{i}$가 공백을 사이로 두고 주어집니다. 이것은 $i$번 스트랩에는 단자가 $A_{i}$개 있으며, 그 스트랩을 장착했을 때의 행복도가 $B_{i}$임을 나타냅니다.

출력

표준 출력의 첫 번째 줄에 스트랩들을 적당히 연결하여 만들 수 있는 휴대전화에 연결된 스트랩들의 행복도의 총 합의 최댓값을 출력합니다.

제약 조건

모든 입력은 아래 조건을 만족합니다.

• $1 \le N \le 2,000$
• $0 \le A_{i} \le N$ ($1 \le i \le N$)
• $-1,000,000 \le B_{i} \le 1,000,000$ ($1 \le i \le N$)

서브태스크

서브태스크 1 [5점]

• $N \le 15$

서브태스크 2 [5점]

• $B_{i} \ge 0$ ($1 \le i \le N$)

서브태스크 3 [45점]

• $A_{i} \le 15$ ($1 \le i \le N$)

서브태스크 4 [45점]

추가 제약 조건이 없습니다.

예제

이 입력의 경우 아래와 같이 달면 행복도의 총 합은 5가 되며 이것이 최대입니다.

• 2번 스트랩을 휴대전화에 직접 설치합니다.
• 1번 스트랩을 2번 스트랩의 단자에 장착합니다.
• 5번 스트랩을 2번 스트랩의 단자에 장착합니다.

이 입력의 경우 모든 스트랩의 행복도가 0 미만이므로, 설치하지 않아야 총합이 최대가 됩니다.