퀠링 블레이드

한 영웅이 게임을 하고 있으며, 이 게임에서 가장 강한 무기는 퀠링 블레이드이다. 모든 종류의 무기는 효용치 $B$와 비용 $C$를 가진다. 효용치는 서로 더해진다. 예를 들어 효용치가 $3$과 $5$인 무기 두 개를 보유하면 현재 효용치는 $3 + 5 = 8$이다. 같은 종류의 무기를 여러 개 보유하면 그 효용치도 각각 더해진다.

어떤 무기를 사려면 먼저 다른 무기가 필요할 수 있다. 예를 들어 어떤 무기가 데몬 엣지 두 개를 필요로 한다면, 그 무기를 사기 전에 데몬 엣지 두 개를 이미 보유하고 있어야 한다. 같은 무기를 한 개 더 사려면 데몬 엣지 두 개가 또 필요하다. 필요 조건으로 쓰인 무기는 구매 후에도 사라지지 않으며, 한 무기가 같은 종류의 무기를 여러 개 필요로 할 수도 있다. 각 무기 종류는 최대 하나의 다른 무기 종류에만 필요 조건으로 쓰이므로, 필요 조건 관계는 퀠링 블레이드를 뿌리로 하는 트리를 이룬다.

영웅은 매초 정확히 $1$코인을 벌어 무기를 사는 데 쓴다. 비용이 $C$인 무기는 쓰지 않은 코인이 $C$개 모이면 살 수 있다. 필요한 모든 하위 무기의 값을 치러야 하므로, 퀠링 블레이드를 얻기까지의 최소 시간은 사야 하는 모든 무기의 비용 합과 같고, 유효한 구매 순서라면 어떤 순서를 따르더라도 이 최소 시간을 달성할 수 있다.

영웅은 완벽주의자다. 이 최소 시간 안에 퀠링 블레이드에 도달하는 모든 구매 순서 중에서 효용(utility)을 최대로 만들고자 한다. 효용은 게임 시작부터 퀠링 블레이드를 얻는 그 초 직전까지(그 초는 포함하지 않는다) 매초마다 현재 보유한 총 효용치를 모두 더한 값이다. 달리 말하면, 구매가 시각 $t$에 완료되는 무기는 퀠링 블레이드를 얻기 전까지 남은 $S - t$초 동안 매초 자신의 효용치를 기여한다. 여기서 $S$는 전체 구매 시간이다.

가능한 최대 효용을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 대부분의 테스트 케이스는 작다.

각 테스트 케이스의 첫 줄에는 무기 종류의 수 $N$이 주어진다 $(1 \le N \le 1000)$.

이어서 무기들을 하나씩 설명한다. 무기 $i$에 대해(무기는 $1$번부터 $N$번까지 번호가 매겨진다):

• 효용치 $B$와 비용 $C$를 나타내는 두 정수가 한 줄에 주어진다 $(1 \le B, C \le 2^{31}-1)$.
• 이 무기가 필요로 하는 서로 다른 무기 종류의 수 $P$가 한 줄에 주어진다.
• 이어지는 $P$개의 줄에는 각각 두 정수 $I$와 $A$가 주어지며, 이 무기가 종류 $I$인 무기를 $A$개 필요로 함을 뜻한다.

$1$번 무기가 퀠링 블레이드이다. 퀠링 블레이드 하나를 얻기 위해 사야 하는 무기의 총 개수는 $10^6$개 미만이며, 각 무기 종류는 최대 하나의 다른 무기 종류에만 필요 조건으로 쓰인다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고 $y$는 최대 효용이다. 답은 항상 부호 있는 64비트 정수 범위에 들어간다.