노천 채굴

시간 제한1초메모리 제한512 MB

요약

각 블록의 가치와 채굴 비용, 그리고 먼저 캐야 하는 선행 관계가 주어질 때, 이 관계에 닫힌 부분집합 중 이익이 최대인 것을 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 최소 신장 트리, 그리디, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

노천 채굴은 땅 표면에 구덩이를 파서 암석이나 광물을 캐내는 방식이다. 상업적으로 쓸모 있는 광맥이 지표 가까이에 있을 때 쓴다. 채굴 회사 ACM은 노천 채굴로 얻는 이익을 최대로 늘리려 한다. ACM은 땅의 정보를 읽어 ACM이 얻을 수 있는 최대 이익을 구하는 프로그램을 여러분에게 맡겼다.

땅 하나는 블록의 집합으로 나타낸다. 블록 $i$ 에는 가치 $v_i$ 가 있고, 그 블록을 파내는 데 비용 $c_i$ 가 든다. 어떤 블록은 다른 블록을 덮고 있다. 블록 $j$ 와 블록 $k$ 가 블록 $i$ 를 덮고 있다면, 블록 $i$ 를 파내기 전에 블록 $j$ 와 블록 $k$ 를 먼저 파내야 한다. 덮고 있는 블록이 하나도 남지 않은 블록만 파낼 수 있다.

파낸 블록 집합에서 얻는 이익은 그 블록의 가치 합에서 비용 합을 뺀 값이다. 언제든 채굴을 멈춰도 되고, 한 블록도 파내지 않으면 이익은 0이다.

입력

첫째 줄에 블록의 개수를 나타내는 정수 $N$ 이 주어진다 ( $1 \le N \le 200$ ). 블록의 번호는 1번부터 $N$ 번까지이다.

다음 $N$ 개의 줄에 블록의 정보가 주어진다. 그중 $i$ 번째 줄은 블록 $i$ 를 설명하며, 먼저 블록 $i$ 의 가치 $v_i$ 와 비용 $c_i$ 가 온다 ( $0 \le v_i, c_i \le 200$ ). 이어서 세 번째 정수 $m_i$ 가 블록 $i$ 가 덮고 있는 블록의 개수를 나타낸다 ( $0 \le m_i \le N - 1$ ). 그 뒤에는 블록 $i$ 가 덮고 있는 블록의 번호 $m_i$ 개가 공백을 사이에 두고 온다. 이 번호는 서로 다르고, 1 이상 $N$ 이하이며, $i$ 는 들어 있지 않다.

순서를 적절히 잡으면 모든 블록을 파낼 수 있다. 모든 블록에 대한 $m_i$ 의 합은 500 이하이다.

출력

ACM이 주어진 땅에서 얻을 수 있는 최대 이익을 정수 하나로 출력한다.

예제4

예제 1

입력

예상 출력

예제 2
입력
```
1
0 5 0
```
예상 출력
```
0
```
예제 3
입력
```
1
200 0 0
```
예상 출력
```
200
```

예제 4

입력

예상 출력