Help Bob

Bob loves pizza but is always short on money. One day he reads that his favorite restaurant, Alfredo's Pizza Restaurant, is running a competition: they will give a large pizza to the first person who tells them the lowest achievable price per unit of area, where each pizza may be bought at most once.

"That's easy!", Bob thinks. "For each pizza I just divide its price by its area, and the smallest quotient is the answer." Unfortunately the problem is trickier. Some pizzas come with discount coupons for other pizzas, and these coupons stack — they can be combined. The pizzas must be bought one after another, and a coupon may only be used on a pizza that has not been bought yet; you cannot apply a discount retroactively to a pizza you already own.

You buy some non-empty set of pizzas (each at most once), paying the discounted price of each. The price per area of your purchase is the total price you pay divided by the total area of all pizzas you bought. Help Bob find the smallest price per area he can achieve.

The input contains several test cases. Each test case starts with an integer $m$ ($1 \le m \le 15$), the number of pizzas Alfredo offers. The input is terminated by a line with $m = 0$, which must not be processed.

Each test case then has $m$ lines. The $i$-th line ($1 \le i \le m$) describes pizza $i$ and begins with three integers $p_i$, $a_i$ and $n_i$: the price of the pizza ($1 \le p_i \le 10000$), its area ($1 \le a_i \le 10000$), and the number of discount coupons you receive when you buy it ($0 \le n_i < m$). Then follow $n_i$ pairs of integers $x_{i,j}$ and $y_{i,j}$: buying pizza $i$ yields a coupon for pizza $x_{i,j}$ ($1 \le x_{i,j} \le m$, $x_{i,j} \ne i$) giving a discount of $y_{i,j}$ percent ($1 \le y_{i,j} \le 50$). For each $i$ the values $x_{i,j}$ are pairwise distinct.

For each test case, print one line with the lowest achievable price per area: the minimum, over every non-empty set of purchased pizzas and every purchase order, of (total price paid) / (total area bought). Round this value to exactly 4 digits after the decimal point.

Coupons combine multiplicatively. For example, a pizza with base price 10 that receives a 50 percent and a 20 percent coupon before it is bought costs $10 \times 0.5 \times 0.8 = 4$.