Hide

# Problem GGet-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.
After falling for a large number of fake get-rich-quick schemes, Marika is in serious need for cash, and really needs a get-rich-quick scheme. Instead of listenting to the ideas of strangers, Marika asked her mathematically talented friend David for some help. David suggested the following scheme, based on a feature of certain credit cards, called cashback.

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}$.

Sample Input 1 Sample Output 1
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

Hide