Minimum Total Purchase Cost with Discount Packages

You are given n items with individual prices and m discount packages. Each discount package applies to a specific set of items and offers a discounted bundle price. More formally, for each discount package, you are given a number k, a list of k distinct 1-indexed item indices, and a discounted price. You may choose to purchase items individually at their listed price or buy them as part of a discount package. Each discount package can be used at most once and only if none of its items have been purchased individually already.

Your task is to compute the minimum total cost required to purchase all n items. Formally, if we denote the set of items by \(I=\{1,2,\dots, n\}\), and a discount package as a triple \((k, S, c)\) where \(S\subset I\) and \(c\) is the discounted price, you need to choose a set of packages and individual purchases such that the union of items covers \(I\) and the total cost is minimized.

Note: All indices used in discount packages are 1-indexed.

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains an integer n, the number of items.
The second line contains n space-separated integers, representing the price of each item.
The third line contains an integer m, the number of discount packages.
Then m lines follow, each describing a discount package. Each line starts with an integer k (the number of items in the package), followed by k space-separated integers (the 1-indexed item indices), and ends with an integer representing the discounted price of that package.

outputFormat

The output is a single integer printed on standard output (stdout) - the minimum total cost to purchase all n items.

3
100 200 300
2
2 1 2 270
3 1 2 3 500

500