Maximizing Net Profit for Space Flight Experiments

Professor W is planning a series of space flights for the National Space Agency. Each flight can conduct a series of commercial experiments to generate profits. There is a set of experiments \(E = \{E_1, E_2, \dots, E_m\}\) and a set of instruments \(I = \{I_1, I_2, \dots, I_n\}\). Each experiment \(E_j\) requires a subset \(R_j \subseteq I\) of instruments. Configuring instrument \(I_k\) costs \(c_k\) dollars, and the sponsor for experiment \(E_j\) will pay \(p_j\) dollars if it is conducted.

The task is to determine which experiments to perform (and thereby which instruments to configure) in a single space flight to maximize the net profit. The net profit is defined as the total sponsorship received from the experiments minus the total cost of configuring the instruments (an instrument is purchased only once even if used by multiple experiments).

This problem can be transformed into a maximum flow / minimum cut formulation. Construct a directed graph as follows:

• Create a source node \(s\) and a sink node \(t\).
• For each experiment \(E_j\) (with \(1 \le j \le m\)), add an edge from \(s\) to the experiment node with capacity \(p_j\).
• For each instrument \(I_k\) (with \(1 \le k \le n\)), add an edge from the instrument node to \(t\) with capacity \(c_k\).
• For each experiment \(E_j\) and each instrument \(I_k\) in its requirement \(R_j\), add an edge from the experiment node to the instrument node with infinite (or very large) capacity.

The maximum net profit is then given by

[ \text{Net Profit} = \sum_{j=1}^m p_j - \text{MaxFlow}(s, t). ]

inputFormat

The input consists of several lines:

1. The first line contains two integers \(m\) and \(n\) representing the number of experiments and instruments respectively.
2. The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\), where \(c_k\) is the cost of instrument \(I_k\).
3. Then follow \(m\) lines, each describing an experiment \(E_j\): the line starts with an integer \(p_j\) (the sponsorship amount), followed by an integer \(k_j\) indicating the number of instruments required, and then \(k_j\) integers representing the indices of the instruments (1-indexed) required by \(E_j\>.

outputFormat

Output a single integer, the maximum net profit that can be achieved for the space flight.

sample

3 4
3 3 3 3
10 2 1 2
5 2 2 3
7 2 1 4

8