Un vendedor tiene $n$ artículos a la venta para un único comprador. El comprador tiene un perfil de valoración $\bar{v} = (v_1, \dots, v_n)$, donde $v_j \geq 0$ denota su valor para el artículo $j$.

El vendedor puede establecer un precio $\bar{p}$, es decir, un vector de precios de artículos $(p_1, \dots, p_n)$. Dada una fijación de precios $\bar{p}$, la utilidad de comprar el artículo $j$ es $v_j - p_j$. El comprador comprará un único artículo $j$ que maximice su utilidad, o nada si su utilidad al comprar cualquier artículo fuera negativa. Si hay varios artículos con la misma utilidad máxima, elegirá aquel con el precio mínimo. Los ingresos del vendedor se definen como el precio del artículo que compra el comprador, y si el comprador no compra nada, los ingresos son 0.

Ahora sabemos que el perfil de valoración $\bar{v}$ se extrae de una distribución conjunta $F$ que define la probabilidad de cada valor posible de $\bar{v}$. Desafortunadamente, no conocemos $F$. En cambio, conocemos las distribuciones marginales $F_1, F_2, \dots, F_n$: la distribución $F_i$ define la probabilidad de $v_i = x$ para cada $x$ posible. Pero no sabemos cómo están correlacionadas: los valores no son necesariamente independientes, por lo que las probabilidades individuales de $v_i = x$ y $v_j = y$ no definen la probabilidad de que ambos ocurran simultáneamente. Tenga en cuenta que la distribución conjunta $F$ es sobre el perfil de valoración $\bar{v}$ y que la distribución marginal $F_i$ es sobre el valor $v_i$ del artículo $i$.

Dada la fijación de precios $\bar{p}$ y las distribuciones marginales $F_1, F_2, \dots, F_n$, se nos pide calcular los ingresos esperados mínimos entre todas las distribuciones conjuntas posibles. Formalmente, sea $\mathcal{F}$ el conjunto de distribuciones conjuntas sobre perfiles de valoración $\bar{v}$ cuyas distribuciones marginales para los valores individuales de los artículos son simplemente $F_1, F_2, \dots, F_n$. Sea $\text{Rev}(\bar{p}, F)$ los ingresos esperados del vendedor al establecer una fijación de precios $\bar{p}$, si el perfil de valoración $\bar{v}$ se extrae de una distribución conjunta $F$. Se nos pide calcular

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

Entrada

La primera línea contiene un único número entero $n$ ($1 \leq n \leq 10^5$), el número de artículos a la venta.

La segunda línea contiene $n$ números enteros no negativos $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq 10^5$), el vector de precios $\bar{p}$.

Las siguientes $n$ líneas describen las distribuciones marginales $F_1, F_2, \dots, F_n$. Cada línea comienza con un número entero $k$: el tamaño del soporte (número de valores diferentes) de $F_i$. Luego siguen $k$ pares de números $q_j$ y $v_j$ ($0 \leq q_j \leq 1$, $0 \leq v_j \leq 10^6$), lo que significa que $F_i$ tiene una probabilidad de $q_j$ de tener el valor $v_j$. Los valores $v_j$ pueden darse como fracciones decimales o en notación científica. Se garantiza que $\sum_{j=1}^k q_j = 1$.

La suma total de los valores de $k$ en estas $n$ líneas no excederá $3 \cdot 10^5$. El tamaño total de la entrada no excederá 5 mebibytes.

Salida

Imprima un único número real: los ingresos esperados mínimos entre todas las distribuciones conjuntas posibles. Su respuesta se considerará correcta si y solo si su error absoluto o relativo no excede $10^{-6}$.

Ejemplos

Entrada 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

Salida 1

2.0000000000

Entrada 2

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

Salida 2

0.0000000000

Entrada 3

1
5
1 1.0 5

Salida 3

5.0000000000