시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 0 0 0 0.000%

문제

Fitting a function to a given finite set of points sampled from an unknown function $F : \mathbb{R} \rightarrow \mathbb{R}$ is a basic problem in mathematics. Typical one is to find a linear function $\overline { F }$ that fits the sampled point best. One way to measure how well $\overline { F }$ fits the sample points is defined as follows. Suppose that $F$ is sampled at $x_1, \dots , x_n$, with $x_1 < \cdots < x_n$. Then the error of $\overline { F }$ is

$\text{error}(F,\overline{F}) = \max_{1 \le i \le n} { \left| F(x_i) - \overline{F}(x_i) \right| }$

Unfortunately, the function values at the sample points are not known exactly. Instead, we have a discrete probability distribution for each $F(x_i)$, that is, we have a discrete set $y_{i,1}, \dots , y_{i,m_i}$ of possible values with associated probabilities $p_{i,j}$ such that $Pr\left[ F(x_i) = y_{i,j} \right] = p_{i,j}$. We define the error measure in the following natural way using the concept of the expected value:

$\text{ error }(F,\overline { F } )=\max _{ 1\le i\le n }{ \left\{ E \left[ \left| F(x_{ i })-\overline { F } (x_{ i }) \right| \right] \right\} }$

The goal is now to find a linear function $\overline{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.

입력

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 ⩽ 105). 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 xi and mi where xi is the value at which we sample the function and mi is the size of distribution (1 ⩽ mi ⩽ 10 and 0 ⩽ xi ⩽ 109). Then it is followed by a list of mi non-negative numbers being less than 109 which are the function values at xi, and finally a list of mi 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.

출력

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

예제 입력 1

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


예제 출력 1

0.5