불확실한 표본에 직선 맞추기

알 수 없는 함수 $F : \mathbb{R} \to \mathbb{R}$에서 얻은 유한한 표본점 집합에 함수를 맞추는 것은 수학의 기본 문제다. 가장 흔한 형태는 표본점에 가장 잘 맞는 일차함수 $\overline{F}$를 찾는 것이다. $F$를 $x_1 < x_2 < \dots < x_n$에서 표본으로 얻었다고 하자. $\overline{F}$가 표본점에 얼마나 잘 맞는지는 다음 오차로 잴 수 있다.

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

그런데 표본점에서의 함숫값을 정확히 알지 못한다. 대신 각 $F(x_i)$의 이산확률분포를 알고 있다. 즉 가능한 값 $y_{i,1}, \dots, y_{i,m_i}$와 그 확률 $p_{i,j}$가 주어지고, $\Pr[F(x_i) = y_{i,j}] = p_{i,j}$이다. 이때 오차는 기댓값을 써서 다음과 같이 정의한다.

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

이 오차를 최소로 만드는 일차함수 $\overline{F}(x) = ax + b$를 찾아, 그 최소 오차를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 표본점의 개수 $n$이 주어진다 ($1 \le n \le 10^5$). 다음 $n$개의 줄에는 표본점의 정보가 $x$가 증가하는 순서로 한 줄에 하나씩 주어진다. $i$번째 표본점의 줄은 함수를 표본으로 얻은 위치 $x_i$와 분포의 크기 $m_i$로 시작한다 ($0 \le x_i \le 10^9$, $1 \le m_i \le 10$). 이어서 $x_i$에서 가능한 함숫값 $m_i$개 $y_{i,1}, \dots, y_{i,m_i}$가 주어지고 ($0 \le y_{i,j} < 10^9$), 마지막으로 확률 $m_i$개 $p_{i,1}, \dots, p_{i,m_i}$가 주어진다 ($0 \le p_{i,j} \le 100$). 실제 확률은 $p_{i,j}$를 100으로 나눈 값이고, 표본점 하나마다 확률 $m_i$개의 합은 100이다. 모든 값은 정수이고 $x_1 < x_2 < \dots < x_n$이다. 입력의 마지막 줄에는 0이 하나 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 최소 오차를 소수점 아래 한 자리까지 반올림해 한 줄에 출력한다. 정확히 중간인 값은 올린다. 예를 들어 0.25는 0.3으로 출력한다.