Minimum Purchase Cost with Promotional Bundles

You are given a list of products with their unit prices, a set of promotional bundles, and a purchase list specifying the exact quantity of each product required. Each promotion bundle offers a discounted price for a specific combination of products. Note that you cannot purchase extra items just to use a promotion even if it reduces the total cost.

For example, consider the following promotion bundles:

• Three flowers for \(5\) instead of \(6\) (normal cost: \(3\times2=6\)).
• Two vases and one flower for \(10\) instead of \(12\) (normal cost: \(2\times5+1\times2=12\)).

If a customer wants to buy three flowers and two vases, one optimal solution is to purchase the bundle of two vases and one flower for \(10\) and then buy the remaining two flowers at the individual price (\(2\) each), giving a total cost of \(14\).

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(m\), representing the number of products and the number of promotional bundles.
2. The next \(n\) lines each contain a string and an integer, representing a product name (consisting of lowercase letters without spaces) and its unit price.
3. The next \(m\) blocks describe the promotional bundles. Each block begins with an integer \(k\) (the number of product types in the bundle), followed by \(k\) pairs. Each pair consists of a product name and the quantity required for that bundle, and then an integer representing the discounted price for that bundle.
4. The last line contains \(n\) integers representing the quantities of each product required (in the same order as the products were given).

outputFormat

Output a single integer, the minimum total cost to exactly purchase the required products using any combination of promotional bundles and individual purchases.

sample

2 2
flower 2
vase 5
1 flower 3 5
2 vase 2 flower 1 10
3 2

14