21080번 - Revenue 스페셜 저지다국어

문제

There is a seller who has $n$ items for sale to a single buyer. The buyer has a valuation profile $\bar{v} = (v_1, \ldots, v_n),ドル where $v_j \ge 0$ denotes her value for item $j$.

The seller can set a pricing $\bar{p},ドル that is, a vector of item prices $(p_1, \ldots, p_n)$. Given a pricing $\bar{p},ドル the utility of buying item $j$ is $v_j - p_j$. The buyer will purchase a single item $j$ that maximizes her utility, or nothing if her utility from purchasing any item would be negative. If there are multiple items with the same maximal utility, she will choose the one with the minimal price. The revenue of the seller is defined as the price of the item that the buyer buys, and if the buyer buys nothing, the revenue is 0ドル$.

Now we know that the valuation profile $\bar{v}$ is drawn from a joint distribution $F$ which defines the probability of every possible value of $\bar{v}$. Unfortunately, we do not know $F$. Instead, we know the marginal distributions $F_1, F_2, \ldots, F_n$: distribution $F_i$ defines the probability of $v_i = x$ for every possible $x$. But we do not know how they are correlated: the values are not necessarily independent, so the individual probabilities of $v_i = x$ and $v_j = y$ don't define the probability of both happening simultaneously. Note that the joint distribution $F$ is over the valuation profile $\bar{v}$ and that the marginal distribution $F_i$ is over the value $v_i$ of item $i$.

Given the pricing $\bar{p}$ and the marginal distributions $F_1, F_2, \ldots, F_n,ドル we are now asked to compute the minimal expected revenue among all possible joint distributions. Formally, let $\mathcal{F}$ be the set of joint distributions over valuation profiles $\bar{v}$ whose marginal distributions for the individual item values are just $F_1, F_2, \ldots, F_n$. Let $\mathrm{Rev} (\bar{p}, F)$ be the seller's expected revenue from setting a pricing $\bar{p},ドル if the valuation profile $\bar{v}$ is drawn from a joint distribution $F$. We are asked to compute $$\min_{F \in \mathcal{F}} \mathrm{Rev}(\bar{p}, F)\text{.}$$

입력

The first line contains a single integer $n$ (1ドル \le n \le 10^5$), the number of items for sale.

The second line contains $n$ non-negative integers $p_1, p_2, \ldots, p_n$ (0ドル \le p_i \le 10^5$), the pricing vector $\bar{p}$.

Next $n$ lines describe the marginal distributions $F_1, F_2, \ldots, F_n$. Each line starts with an integer $k$: the support size (number of different values) of $F_i$. Then follow $k$ pairs of numbers $q_{j}$ and $v_{j}$ (0ドル \le q_{j} \le 1,ドル 0ドル \le v_{j} \le 10^6$), meaning that $F_i$ has probability of $q_{j}$ to have value $v_{j}$. The values $v_{j}$ may be given as decimal fractions or in scientific notation. It is guaranteed that $\sum_{j = 1}^{k} q_{j} = 1$.

The total sum of the values of $k$ on these $n$ lines will not exceed 3ドル \cdot 10^5$. The total size of the input will not exceed 5ドル$ mebibytes.

출력

Output a single real number: the minimal expected revenue among all possible joint distributions. Your answer will be considered correct if and only if its absolute or relative error does not exceed 10ドル^{-6}$.

제한

힌트