Продавец предлагает $n$ товаров одному покупателю. У покупателя есть профиль оценки $\bar{v} = (v_1, \dots, v_n)$, где $v_j \ge 0$ обозначает ценность для него товара $j$.

Продавец может установить цены $\bar{p}$, то есть вектор цен на товары $(p_1, \dots, p_n)$. При заданных ценах $\bar{p}$ полезность покупки товара $j$ равна $v_j - p_j$. Покупатель приобретет один товар $j$, который максимизирует его полезность, или не купит ничего, если полезность от покупки любого товара будет отрицательной. Если существует несколько товаров с одинаковой максимальной полезностью, он выберет тот, у которого минимальная цена. Выручка продавца определяется как цена товара, который покупает покупатель, а если покупатель ничего не покупает, выручка равна 0.

Теперь мы знаем, что профиль оценки $\bar{v}$ выбирается из совместного распределения $F$, которое определяет вероятность каждого возможного значения $\bar{v}$. К сожалению, мы не знаем $F$. Вместо этого нам известны маргинальные распределения $F_1, F_2, \dots, F_n$: распределение $F_i$ определяет вероятность $v_i = x$ для каждого возможного $x$. Но мы не знаем, как они коррелируют: значения не обязательно независимы, поэтому индивидуальные вероятности $v_i = x$ и $v_j = y$ не определяют вероятность того, что оба события произойдут одновременно. Заметим, что совместное распределение $F$ задано на профиле оценки $\bar{v}$, а маргинальное распределение $F_i$ — на значении $v_i$ товара $i$.

При заданных ценах $\bar{p}$ и маргинальных распределениях $F_1, F_2, \dots, F_n$ требуется вычислить минимальную ожидаемую выручку среди всех возможных совместных распределений. Формально, пусть $\mathcal{F}$ — множество совместных распределений профилей оценки $\bar{v}$, маргинальные распределения которых для индивидуальных значений товаров в точности равны $F_1, F_2, \dots, F_n$. Пусть $\text{Rev}(\bar{p}, F)$ — ожидаемая выручка продавца при установке цен $\bar{p}$, если профиль оценки $\bar{v}$ выбирается из совместного распределения $F$. Нам нужно вычислить:

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

Входные данные

Первая строка содержит целое число $n$ ($1 \le n \le 10^5$), количество товаров для продажи.

Вторая строка содержит $n$ неотрицательных целых чисел $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^5$), вектор цен $\bar{p}$.

Следующие $n$ строк описывают маргинальные распределения $F_1, F_2, \dots, F_n$. Каждая строка начинается с целого числа $k$: размер носителя (количество различных значений) $F_i$. Затем следуют $k$ пар чисел $q_j$ и $v_j$ ($0 \le q_j \le 1$, $0 \le v_j \le 10^6$), означающих, что в $F_i$ вероятность значения $v_j$ равна $q_j$. Значения $v_j$ могут быть заданы в виде десятичных дробей или в экспоненциальной записи. Гарантируется, что $\sum_{j=1}^k q_j = 1$.

Суммарное значение $k$ по этим $n$ строкам не превышает $3 \cdot 10^5$. Общий размер входных данных не превышает 5 мебибайт.

Выходные данные

Выведите единственное вещественное число: минимальную ожидаемую выручку среди всех возможных совместных распределений. Ваш ответ будет считаться верным, если его абсолютная или относительная погрешность не превышает $10^{-6}$.

Примеры

Пример 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

2.0000000000

Пример 2

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

0.0000000000

Пример 3

1
5
1 1.0 5

5.0000000000