Team Composition Optimization

In this problem, you are given n heroes (with n < 31) and each hero i has a positive integer contribution value \(v_i\). In a match, you must choose exactly 6 heroes to form your team. Note that heroes can be chosen with repetition allowed (i.e. you may choose the same hero more than once).

The total team ability is defined as the sum of the contributions of the individual heroes plus some bonus. In particular, there are \(m\) bonus groups. For each bonus group, you are given a list of heroes and an integer bonus value \(x\). For a bonus group, if your team contains all heroes in that group, you gain an extra \(x\) for each complete occurrence of that group. A complete occurrence is counted as \(\min(\text{frequency of each hero in the group})\). Note: if a bonus group can be formed more than once (i.e. the heroes in that group appear multiple times), then the bonus is counted for each occurrence.

Your task is to select 6 heroes (with repetition allowed) from the available n heroes so that the total team ability is maximized.

The total ability is computed by: \[ \text{Total Ability} = \sum_{i=1}^{n} c_i \times v_i + \sum_{j=1}^{m} \Big(\min_{h \in S_j} \; c_h\Big) \times x_j, \] where \(c_i\) is the number of times hero \(i\) is selected, \(S_j\) is the set of heroes in the \(j\)th bonus group, and \(x_j\) is the bonus value for that group.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of available heroes and \(m\) is the number of bonus groups.

The second line contains \(n\) positive integers: \(v_1, v_2, \dots, v_n\) representing the contribution of each hero.

Then follow \(m\) lines. Each of these lines describes one bonus group in the following format:

k a1 a2 ... ak x

Here, \(k\) is the number of heroes in the bonus group, \(a1, a2, \dots, ak\) are the indices (1-indexed) of the heroes in that group, and \(x\) is the bonus value for that group.

outputFormat

Output a single integer – the maximum total ability of the team that can be achieved by choosing exactly 6 heroes (with repetition allowed).

sample

3 1
1 2 3
2 1 2 10

39