안전 예방 조치

석유 시추 시설(다른 여러 공장이나 생산 설비도 마찬가지)의 폭발은 여러 단계로 이루어진 안전 시스템으로 예방하도록 되어 있다. 예를 들어 어떤 배관에서 기름이 새더라도, 그 주위를 감싸는 또 다른 배관이 기름을 받아 내면 큰 문제가 되지 않을 수 있다. 안전 밸브 같은 장치가 있으면 높은 압력도 큰 손상을 일으키지 않는다. 좋은 공학의 상당 부분은 이처럼 안전성을 시스템 자체에 자연스럽게 녹여 넣는 데 있다. 이런 좋은 설계를 유도하기 위해 정부는 심해 시추 시설을 지을 때 지켜야 할 안전 규정을 정해 두곤 한다. 다만 규정이 실제로 효과를 내려면 집행이 뒷받침되어야 하는데, 지난 몇 년 동안은 그 집행이 충분하지 못했다.

이런 시스템의 안전 문제를 단순하게 모형화하면 다음과 같다. 각 부품은 동작을 위해 다른 부품에 의존할 수 있으며, 고장 날 수 있다. 어떤 부품은 스스로 고장 나기도 하고, 어떤 부품은 자신이 의존하는 부품 가운데 일부가 먼저 고장 났을 때에만 고장 난다. 문제를 단순하게 하기 위해, 부품 사이의 의존 관계에는 절대 순환이 없다고 가정한다. 각 부품 $i$ 에는 임계값 $t_i \ge 0$ 이 정해져 있으며, 이는 자신이 의존하는 부품 중 적어도 $t_i$ 개가 이미 고장 났을 때에만 부품 $i$ 가 고장 날 수 있음을 뜻한다. 따라서 $t_i = 0$ 인 부품은 스스로 고장 날 수 있다.

이제 각 부품에 안전 기술을 적용할 수 있다. 부품 $i$ 에 이 기술을 적용하는 비용은 실수 $p_i \ge 0$ 이다. 비용을 지불하고 부품 $i$ 에 안전 기술을 더하면, 그 부품이 의존하는 다른 부품이 모두 고장 나더라도 부품 $i$ 는 절대 고장 나지 않는다. 우리의 목표는 지정된 특정 부품이 고장 나지 않도록 지키는 것이다. 이 부품이 고장 나는 것이 곧 시추 시설이 폭발하는 상황에 해당한다고 생각하면 된다. 물론 이를 가능한 한 가장 낮은 총비용으로 달성하고자 한다.

첫째 줄에 데이터 집합의 개수 $K$ 가 주어진다. 그 뒤로 $K$ 개의 데이터 집합이 이어지며, 각 데이터 집합의 형식은 다음과 같다.

각 데이터 집합의 첫째 줄에는 시스템에 있는 부품의 개수를 나타내는 정수 $n$ ($1 \le n \le 20$) 이 주어진다. 우리가 지켜야 하는 부품은 항상 부품 $n$ 이다.

이어서 $n$ 개의 줄이 주어지며, 각 줄은 하나의 부품을 설명한다. $i$ 번째 줄의 첫 번째 수는 부품 $i$ 의 임계값 $t_i$ 이고, 두 번째 수(실수)는 그 부품을 보호하는 비용 $p_i$ 이다. 줄에 남은 수들은 부품 $i$ 가 의존하는 (0개 이상의) 다른 부품들의 번호이다. 이 번호들은 모두 $i$ 보다 반드시 작으며, 따라서 의존 관계에 순환이 생기지 않는다.

각 데이터 집합마다, 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 $x$ 는 데이터 집합의 번호이다. 다음 줄에는 부품 $n$ 이 고장으로부터 완전히 보호되도록 하는 최소 비용을 소수점 아래 둘째 자리까지 반올림하여 출력한다. 연속한 두 데이터 집합 사이에는 빈 줄을 하나 출력한다.