Photo Session Profit Maximization

Little B has \(N\) subordinates. He wants to take photos with some of his subordinates for several customers. There are \(M\) customers. Each customer is willing to pay a certain amount \(p_i\) to have a photo taken with a specific set of subordinates. However, the photo can only be taken if all the required subordinates are present. Otherwise, no photo will be taken and Little B will not receive any money.

Note: Bringing subordinates is not free! For each subordinate that Little B brings, he has to pay a fee \(w_j\) to ensure their cooperation during the photo session.

You are given the cost \(w_j\) for each subordinate \(1 \leq j \leq N\) and for each customer, the set of required subordinates along with the payment \(p_i\) the customer offers. Determine the maximum profit Little B can achieve by choosing an optimal subset \(S\) of subordinates to bring.

The profit is defined as:

[ \text{profit}(S) = \sum_{i=1}^{M} \mathbf{1}{{R_i \subseteq S}},p_i - \sum{j \in S}w_j, ]

where \(R_i\) is the set of subordinates required by the \(i\)-th customer. If no subordinate is brought, the profit is \(0\).

Find the maximum profit achievable.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of subordinates and the number of customers).

The second line contains \(N\) integers \(w_1, w_2, \ldots, w_N\), where \(w_j\) is the cost for bringing the \(j\)-th subordinate.

Then \(M\) lines follow. Each line describes a customer and contains the following:

• An integer \(k\) denoting the number of subordinates required by this customer.
• Followed by \(k\) distinct integers representing the indices (1-indexed) of the required subordinates.
• Finally, an integer \(p_i\) which is the amount the customer pays if all the required subordinates are brought.

It is guaranteed that \(1 \le N \le 20\) to allow a solution with bitmask enumeration.

outputFormat

Output a single integer, the maximum profit Little B can achieve.

sample

3 3
3 2 1
2 1 3 10
1 2 5
3 1 2 3 15

24