Problem G
Get-Rich-Quick Schemes

Another way of getting rich quick could have been to invest in bitcoin prior to the summer of 2017. Author: Måns Magnusson.

Cashback means that you earn a certain percentage of cash back on purchase you make, depending on the type of purchase. Formally, there are $n$ categories of merchandise. If you purchase merchandise from category $i$ for $x$ SEK, you earn $p_ i \cdot x$ SEK back, up to some maximum limit $m_ i$ in a single month. While this does not help you earn money (since $p_ i < 1$), you realized that you can simply return any products you bought to the store to get the money back.

Things are made more difficult by the fact that a particular store will get suspicious if you return too many products per month. In store $i$, you can buy and return merchandise for at most $a_ i$ SEK before start refusing you as a customer. Furthermore, a particular store only sells merchandise from a set of categories specific to that store. However, it has products costing any real amount of money from each category.

In order to get-rich-quick, Marika wants to earn as much money per month as possible. How much can she earn if she plans her purchases optimally?

Input

The input consists of:

• one line with the integer $n$ ($1 \le n \le 300$), the number of categories.

• $n$ lines with the integers $p_ i$ and $m_ i$ ($0 \le p_ i < 100$, $0 \le m_ i \le 10^9$), the cashback rate (in percent) and the maximum limit of a product. The $i$’th line contains the rate and limit of the $i$’th product.

• one line with the integer $s$ ($1 \le s \le 300$), the number of stores.

• $s$ lines with the integers $l_ i$ and $a_ i$, followed by $a_ i$ distinct integers $k_{i,1}, \dots , k_{i, a_ i}$, ($1 \le l_ i \le 10^9$, $1 \le a_ i \le n$, $1 \le k_{i, j} \le n$) The integers $k_{i, j}$ on the $i$’th line are the numbers of the categories sold by the $i$’th store. The categories are numbered between $1$ and $n$ in the order they are listed in the input.

Output

Output the maximum amount of money Marika can earn per month if purchasing items optimally. Your answer will be considered correct if it has a relative or absolute error of at most $10^{-6}$.

3
10 100
20 50
15 40
5
20 3 1 2 3
20 2 2 3
20 1 2
20 1 3
20 2 1 2

17