시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

David is writing an article for the Bulletin of the Association of Proof Completions. In his article, he proves several theorems. For every theorem, David came up with a proof. Since David is a very eager student, he even came up with multiple proofs for some of the theorems. As usual, a proof for a theorem may depend on a number of other theorems.

The article has to be as short as possible to publish it, and David only really cares about the main theorem, Theorem 0. In order to achieve this, he has estimated the number of words he will need for every proof. Can you help David find the shortest possible length of his article?

입력

  • A single line containing 1 ≤ n ≤ 20, the number of theorems.
  • For each theorem:
    • A single line containing 1 ≤ pi ≤ 10, the number of proofs for the ith theorem.
    • pi lines, each of the form l, k, d0, . . . , dk−1, where 0 ≤ l ≤ 106 is the length of the proof, 0 ≤ k ≤ n − 1 is the number of theorems the proof depends on, and the 0 ≤ di ≤ n − 1 are the numbers of the theorems the proof depends on.

출력

Print one line with a single integer, the shortest possible length of David’s article.

예제 입력 1

2
2
10 0
3 1 1
1
4 1 0

예제 출력 1

10

예제 입력 2

4
2
1 2 1 3
5 1 2
1
2 0
1
0 0
2
2 0
1 1 1

예제 출력 2

4