Line Fiting

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Fitting a function to a given finite set of points sampled from an unknown function F : R → R is a basic problem in mathematics. Typical one is to find a linear function F that fits the sampled point best. One way to measure how well F fits the sample points is defined as follows. Suppose that F is sampled at x1, . . . , xn, with x1 < · · · < xn. Then the error of F is:

 

Unfortunately, the function values at the sample points are not known exactly. Instead, we have a discrete probability distribution for each F(xi), that is, we have a discrete set y_i,1, . . . , y_i,mi of possible values with associated probabilities p_i,j such that Pr [F(x_i) = y_i,j ] = p_i,j . We define the error measure in the following natural way using the concept of the expected value:

The goal is now to find a linear function F = ax + b that minimizes the error. You must write a program that gets the sample points and their probabilities and computes the minimum error defined above.

Input

There are multiple test cases in the input. The first line of each test case contains n, the number of the sampled points (1 ⩽ n ⩽ 10⁵). Next, the information of sampled points (in the increasing order) comes in n lines; one line for each sampled point. For the i-th sampled point, the line starts with two non-negative integer numbers x_i and m_i where x_i is the value at which we sample the function and mi is the size of distribution (1 ⩽ m_i ⩽ 10 and 0 ⩽ x_i ⩽ 10⁹). Then it is followed by a list of mi non negative numbers being less than 10⁹ which are the function values at x_i, and finally a list of m_i probabilities. For simplicity, each given probability p in the input is a non-negative integer less than or equal to 100.

You can get the real probability by dividing p to 100. You can assume the summation of all probability numbers is equal to 100. The input terminates with a line containing 0 which should not be processed.

Output

For each test case, output a line containing the minimum error rounded to exactly one digit after the decimal point.

Sample Input

2
0 2 0 1 50 50
1 2 0 1 50 50
0

Sample Output

0.5

Submit

Source: Tehran, Asia Region - Regional 2014