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.
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?


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 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
10 100
20 50
15 40
20 3 1 2 3
20 2 2 3
20 1 2
20 1 3
20 2 1 2

Please log in to submit a solution to this problem

Log in