\(N\)개의 물건이 있고 물건 \(i\)는 점수 \(s_i\)(음수일 수 있음)를 주며 선수 물건 집합을 가진다. 물건은 하나씩 모으며, 어떤 물건의 모든 선수 물건을 이미 모은 뒤에만 그 물건을 모을 수 있다. 정확히 \(K\)개의 물건을 모아 총점을 최대화하고 그 최댓값을 출력하시오. 선수 물건은 항상 더 낮은 번호의 물건만 가리키므로 물건 \(0 \dots K-1\)을 모으는 것은 항상 가능하다.

첫 줄에 \(N\)과 \(K\)가 주어진다 (\(1 \le N \le 16\), \(0 \le K \le N\)). 이어지는 \(N\)개의 줄은 물건 \(i\)를 나타내며, 점수 \(s_i\) (\(-1000 \le s_i \le 1000\)), 개수 \(c_i\), 그리고 \(c_i\)개의 서로 다른 선수 인덱스(모두 \(< i\))가 주어진다.

최대 총점을 출력한다.

riseoj 작성

출처 RiseOJ Basics