Shopping Offers

In a shop, each kind of product has a price. For example, a flower costs 2 ICU (Informatics Currency Units) and a vase costs 5 ICU. To attract more customers, the shop introduces several special offers.

A special offer bundles one or more products together for a reduced price. For example, three flowers for 5 ICU instead of the usual 6, or two vases together with one flower for 10 ICU instead of the usual 12.

Write a program that computes the lowest price a customer has to pay for a given set of items, making the best possible use of the special offers. You are not allowed to buy extra items that are not on the shopping list, even if doing so would lower the price.

Using the prices and offers above (a flower for 2 ICU, a vase for 5 ICU), the lowest price for three flowers and two vases is 14 ICU: buy two vases and one flower at the reduced price of 10 ICU, and the remaining two flowers at the regular price of 4 ICU.

The first line contains the number $b$ of different kinds of products in the basket ($0 \le b \le 5$). Each of the next $b$ lines contains three integers $c$, $k$, and $p$. The value $c$ is the (unique) product code ($1 \le c \le 999$), $k$ is how many items of this product are in the basket ($1 \le k \le 5$), and $p$ is the regular price per item ($1 \le p \le 999$). In total at most $5 \times 5 = 25$ items can be in the basket.

The next line contains the number $s$ of special offers ($0 \le s \le 99$). Each of the next $s$ lines describes one offer. The first number $n$ on the line is the number of different kinds of products in the offer ($1 \le n \le 5$). The next $n$ pairs of integers $(c, k)$ indicate that $k$ items ($1 \le k \le 5$) of the product with code $c$ ($1 \le c \le 999$) are part of the offer. The last number $p$ on the line is the reduced price of the offer ($1 \le p \le 9999$). The reduced price of every offer is always less than the sum of the regular prices of the products it contains.

Print a single line with the lowest possible price to pay for all the items given in the input.