P2732 [USACO3.3] Shopping Offers

In a store, each type of product has a price (an integer). For example, a flower costs $2$, and a vase costs $5$. To attract more customers, the store runs promotions.

Promotions bundle one or more products and sell them at a discount. For example: Three flowers cost $5$ instead of $6$, and $2$ vases plus $1$ flower cost $10$ instead of $12$. Write a program to compute the cost for a customer to buy certain products, using the offers to minimize the total cost. Even if adding extra products could lower the total cost, you are not allowed to do that. For the products above, the minimum cost to buy three flowers and two vases is: buy the offer of two vases and one flower for $10$, and buy two flowers at the regular price for $4$.

The input file contains some offers provided by the store, followed by a shopping list (at most $5$ types of products). Line $1$: The number of offer types $s$ ($0 \leq s \leq 99$). Lines $2$ to $s+1$: Each line describes one offer using several integers. The first integer $n$ ($1 \leq n \leq 5$) is the number of different products in this offer. Then there are $n$ pairs of integers $c$ and $k$, meaning $k$ ($1 \leq k \leq 5$) units of the product with code $c$ ($1 \leq c \leq 999$) are included in this offer. The last integer $p$ is the offer price ($1 \leq p \leq 9{,}999$). The offer price is always lower than the regular price. Line $s+2$: An integer $b$ ($0 \leq b \leq 5$), the number of different products to buy. Lines $s+3$ to $s+b+2$: Each of these $b$ lines contains three integers $c, k, p$. Here $c$ is the unique product code ($1 \leq c \leq 999$), $k$ is the required quantity of product $c$ ($1 \leq k \leq 5$), and $p$ is the regular price of product $c$ ($1 \leq p \leq 999$). In total, at most $5 \times 5 = 25$ items are to be purchased.

Output a single line with one integer: the minimum total price to purchase these items.

Translation from NOCOW. USACO Training Section 3.3. Translated by ChatGPT 5