Maximum Production of Items via Conversions

You are given n types of items and m conversion methods. Each conversion method is described by three parameters: an input item type \(a_i\), an integer \(k_i\) and k_i distinct output item types \(b_{i,1}, b_{i,2}, ..., b_{i,k_i}\). The i-th conversion allows you to take one item of type \(a_i\) and convert it into one item of each type \(b_{i,1}, b_{i,2}, ..., b_{i,k_i}\). You may use the same conversion method arbitrarily many times.

You also have an initial stock of items. The initial stock is given as \(n\) nonnegative integers; the \(i\)-th integer represents how many items of type \(i\) you initially have.

Your task is: For every item type \(d\) (\(1 \le d \le n\)), determine the maximum number of items of type \(d\) that you can obtain by applying a sequence of conversions optimally. Note that when you apply a conversion on an item, that item is consumed, and you may choose to not convert an item if that is more beneficial for your target.

Note: It is guaranteed that there is no cycle of conversions that increases the quantity of items indefinitely (i.e. the maximum obtainable number for each item is finite).

The underlying recurrence for any item type i (with respect to a target \(d\)) can be defined as follows:

[ G(i, d) = \max\Bigl(\mathbf{1}{{i=d}}, ;\max{\text{conversion rule } r \text{ with input } i}\Bigl{ \sum_{j \in r} G(j,d) \Bigr} \Bigr), ]

where \(\mathbf{1}_{\{i=d\}}\) is 1 if \(i=d\) and 0 otherwise. The final answer for target \(d\) is \[ Ans(d) = \sum_{i=1}^{n} (\text{initial count of type } i) \times G(i,d). \]

inputFormat

The input consists of the following parts:

1. The first line contains two integers \(n\) and \(m\) denoting the number of item types and the number of conversion rules.
2. Then \(m\) lines follow, each describing a conversion rule. A rule is given in the following format:
   \(a\; k\; b_1\; b_2\; \dots\; b_k\)
   where \(a\) is the input type, \(k\) is the number of output types, and \(b_1, b_2, \dots, b_k\) are the distinct output item types.
3. The next line contains \(n\) integers. The \(i\)-th integer indicates the initial number of items of type \(i\).

outputFormat

Output a single line containing \(n\) integers separated by spaces. The \(d\)-th integer should be the maximum number of items of type \(d\) that can be produced using the conversion rules optimally.

sample

3 2
1 2 2 3
2 1 3
1 0 0

1 1 2