오픈소스 버그 잡기

시간 제한4초메모리 제한256 MB

요약

각 버그의 재미 값과 선행 의존 관계가 주어질 때, 어떤 버그를 고치면 그 선행 버그도 함께 고쳐야 한다는 조건 아래 총 재미를 최대로 만드는 집합을 찾는다.

난이도: 보통10점 중 7점
유형: 그래프, 동적 계획법, 그리디, 위상 정렬
정답자: 아직 제출이 없습니다

문제

당신은 취미로 오픈 소스 SDK인 "Le Great SDK" (LG SDK)의 버그를 종종 고친다. 최근 발견된 여러 버그와 그 사이의 연관성 덕분에 재미있는 문제를 하나 풀게 되었다.

현재 신고된 버그는 총 n개이고, 각 버그 리포트를 읽고 나서 각 버그를 고치는 일이 얼마나 재미있을지 수치로 매겼다. 버그에는 1번부터 n번까지 번호가 붙어 있다.

구체적으로 i번 버그를 고치면 재미 f_i를 얻는다. 이 값은 양의 정수일 수도 있고 음의 정수일 수도 있다. 값이 음의 정수라는 것은 그 버그가 너무 지루해서 고치는 과정을 즐기지 못한다는 뜻이다.

흥미도가 양수인 버그만 고칠 수 있으면 좋겠지만, 버그 리포트를 읽어 보니 어떤 버그는 그 버그를 고치려면 다른 버그까지 고쳐야 하는 관계가 있다. 즉, 버그 i를 고치기 위해서는 원하지 않더라도 다른 버그 j를 고쳐야만 버그 i를 온전히 고쳤다고 할 수 있는 경우가 있다.

예를 들어 신고된 버그가 n = 3개이고 흥미도가 f_1 = 5, f_2 = -2, f_3 = 3이라고 하자. 버그 1을 고치려면 버그 2도 함께 고쳐야 하고, 버그 2를 고치는 데는 다른 버그를 고칠 필요가 없다. 마지막으로 버그 3을 고치려면 버그 1, 2를 모두 고쳐야 한다.

이 경우 버그 2만 고치면 총 흥미도는 -2가 되고, 버그 1, 2를 고치면 흥미도가 3이 되어 양수가 된다. 버그 셋을 모두 고치면 총 흥미도는 6이 된다.

버그의 수와 각 버그의 흥미도, 버그 사이의 관계가 주어졌을 때, 흥미도가 최대가 되도록 하는 버그만 고치고 싶다. 이때 달성할 수 있는 흥미도의 최댓값을 구하자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 버그의 수 n이 주어진다. 둘째 줄에는 n개의 정수가 공백으로 구분되어 주어지는데, 이는 각 버그의 흥미도 f_i를 뜻한다.

다음 n줄에 걸쳐 각 줄에 하나 이상의 정수가 주어진다. i번째 줄에 주어진 첫 정수는 i번째 버그를 고치기 위해 몇 개의 다른 버그를 고쳐야 하는지를 나타낸다. 그 수가 x_i라면 같은 줄에 공백으로 구분된 x_i개의 정수가 더 주어지며, 이들이 버그 i를 고치기 위해 함께 고쳐야 하는 다른 버그를 나타낸다. 이때 주어지는 x_i개의 버그는 중복으로 주어지지 않는다.

출력

각 테스트 케이스마다 흥미도의 최댓값을 한 줄에 하나씩 출력한다.

제한

1 ≤ T ≤ 10
2 ≤ n ≤ 500
1 ≤ |f_i| ≤ 1,000,000
0 ≤ x_i ≤ min(300, n-1)

예제1

예제 1

입력

8
4
2 -3 6 -4
1 2
0
2 2 4
1 2
3
2 -6 3
0
0
2 1 2
3
5 -2 3
1 2
0
2 1 2
3
-2 -3 -4
0
0
0
3
1 -1 2
1 2
1 3
1 1
6
-51 -89 -58 21 -6 35
0
4 1 4 3 5
2 4 6
1 1
4 1 4 6 3
1 1
5
-10 -10 -10 -10 39
0
0
0
0
4 1 2 3 4
7
72 96 -45 -69 -46 65 -70
0
1 1
2 1 2
3 1 2 3
2 1 2
4 1 2 3 5
2 3 5

예상 출력