Safety Precautions

Explosions of oil rigs -- and, for that matter, other factories and production systems -- are meant to be prevented by multi-level safety systems. For instance, a pipe leak may not be a problem if another pipe around it can catch the oil. High pressure will not cause major damage if there are relief valves, and so on. A large share of good engineering is building safety into systems naturally. To encourage such good engineering, governments tend to prescribe safety regulations for building deep-water oil rigs. Unfortunately, for such regulations to work they must also be enforced, which has not really been the case over the last few years.

A simplified way to model the safety of a system such as an oil well is the following. Components may depend on other components for their operation, and they can malfunction. Some may malfunction on their own; others malfunction only if some of the components they depend on have already malfunctioned. For simplicity we assume that there are never cycles in the component dependencies. Each component $i$ has a threshold $t_i \ge 0$, meaning that it can only malfunction if at least $t_i$ of the components it depends on have already malfunctioned. Thus, components with $t_i = 0$ can malfunction on their own.

We can equip components with safety technology. For component $i$ the price of this technology is a real number $p_i \ge 0$. If we pay the price and add the technology to component $i$, it will never malfunction, even if all of the other components it depends on do. Our goal is to protect one designated component from malfunctioning; imagine that this component corresponds to the oil rig exploding. Of course, we want to do so at the lowest possible total cost.

The first line contains the number $K$ of data sets. This is followed by $K$ data sets, each of the following form.

The first line of each data set contains an integer $n$ ($1 \le n \le 20$), the number of components in the system. The component we want to protect is always component $n$.

This is followed by $n$ lines, each describing one component. The first number in line $i$ is the threshold $t_i$ of component $i$. The second number (a floating-point number) is the price $p_i$ for protecting the component. The remaining numbers in line $i$ are the indices of the (zero or more) other components that component $i$ depends on. All of them are strictly less than $i$, which also ensures that there are no cycles in the dependencies.

For each data set, output Data Set x: on a line by itself, where $x$ is its number. On the next line, output the minimum cost at which component $n$ can be completely protected from malfunction, rounded to two decimals. Output one blank line between consecutive data sets.