Sprzedawca oferuje $n$ przedmiotów na sprzedaż jednemu kupującemu. Kupujący posiada profil wyceny $\bar{v} = (v_1, \dots, v_n)$, gdzie $v_j \ge 0$ oznacza wartość, jaką przypisuje przedmiotowi $j$.

Sprzedawca może ustalić cennik $\bar{p}$, czyli wektor cen przedmiotów $(p_1, \dots, p_n)$. Przy danym cenniku $\bar{p}$, użyteczność zakupu przedmiotu $j$ wynosi $v_j - p_j$. Kupujący zakupi pojedynczy przedmiot $j$, który maksymalizuje jego użyteczność, lub nie zakupi niczego, jeśli użyteczność zakupu któregokolwiek przedmiotu byłaby ujemna. Jeśli istnieje wiele przedmiotów o tej samej maksymalnej użyteczności, kupujący wybierze ten o najniższej cenie. Przychód sprzedawcy definiuje się jako cenę przedmiotu, który kupuje nabywca; jeśli nabywca nie kupuje niczego, przychód wynosi 0.

Wiemy, że profil wyceny $\bar{v}$ pochodzi z rozkładu łącznego $F$, który określa prawdopodobieństwo każdej możliwej wartości $\bar{v}$. Niestety, nie znamy $F$. Znamy natomiast rozkłady brzegowe $F_1, F_2, \dots, F_n$: rozkład $F_i$ określa prawdopodobieństwo $v_i = x$ dla każdej możliwej wartości $x$. Nie wiemy jednak, w jaki sposób są one skorelowane: wartości niekoniecznie są niezależne, więc indywidualne prawdopodobieństwa $v_i = x$ oraz $v_j = y$ nie definiują prawdopodobieństwa zajścia obu zdarzeń jednocześnie. Należy zauważyć, że rozkład łączny $F$ dotyczy profilu wyceny $\bar{v}$, a rozkład brzegowy $F_i$ dotyczy wartości $v_i$ przedmiotu $i$.

Mając dany cennik $\bar{p}$ oraz rozkłady brzegowe $F_1, F_2, \dots, F_n$, mamy za zadanie obliczyć minimalny oczekiwany przychód wśród wszystkich możliwych rozkładów łącznych. Formalnie, niech $\mathcal{F}$ będzie zbiorem rozkładów łącznych profili wycen $\bar{v}$, których rozkłady brzegowe dla poszczególnych przedmiotów są równe $F_1, F_2, \dots, F_n$. Niech $\text{Rev}(\bar{p}, F)$ będzie oczekiwanym przychodem sprzedawcy przy ustalonym cenniku $\bar{p}$, jeśli profil wyceny $\bar{v}$ pochodzi z rozkładu łącznego $F$. Mamy obliczyć:

$$\min_{F \in \mathcal{F}} \text{Rev}(\bar{p}, F)$$

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 10^5$), liczbę przedmiotów na sprzedaż.

Druga linia zawiera $n$ nieujemnych liczb całkowitych $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^5$), wektor cen $\bar{p}$.

Kolejne $n$ linii opisuje rozkłady brzegowe $F_1, F_2, \dots, F_n$. Każda linia zaczyna się od liczby całkowitej $k$: rozmiaru nośnika (liczby różnych wartości) rozkładu $F_i$. Następnie następuje $k$ par liczb $q_j$ oraz $v_j$ ($0 \le q_j \le 1$, $0 \le v_j \le 10^6$), co oznacza, że w rozkładzie $F_i$ prawdopodobieństwo wystąpienia wartości $v_j$ wynosi $q_j$. Wartości $v_j$ mogą być podane jako ułamki dziesiętne lub w notacji naukowej. Gwarantuje się, że $\sum_{j=1}^k q_j = 1$.

Suma wartości $k$ w tych $n$ liniach nie przekroczy $3 \cdot 10^5$. Całkowity rozmiar danych wejściowych nie przekroczy 5 megabajtów.

Wyjście

Wypisz pojedynczą liczbę rzeczywistą: minimalny oczekiwany przychód wśród wszystkich możliwych rozkładów łącznych. Twoja odpowiedź zostanie uznana za poprawną wtedy i tylko wtedy, gdy jej błąd bezwzględny lub względny nie przekracza $10^{-6}$.

Przykład

Wejście 1

2
2 5
4 0.254 5 0.227 8 0.269 10 0.25 9
4 0.274 9 0.272 9 0.223 8 0.231 7

Wyjście 1

2.0000000000

Wejście 2

2
7 7
2 0.5 1 0.5 0
2 0.3 5 0.7 1

Wyjście 2

0.0000000000

Wejście 3

1
5
1 1.0 5

Wyjście 3

5.0000000000