Student Group Assignment for Minimal Financial Expenditure

There are n students and m study groups. Each student is willing to join only some of these groups and may join at most k groups. When a student joins a study group, the finance office collects a certain commission (which is not directly used in the calculation), and each study group has its own commission rate. On the other hand, if a students join the i-th group, the finance office must pay a reward of \(C_i \times a^2\) dollars for that group.

The primary objective is to have as many students as possible participate (a student is counted only once regardless of how many groups they join). Subject to this, the secondary objective is to minimize the total reward payment. Under the assumption that assigning a student to more than one group does not further increase the number of participating students and only increases the cost (because of the convex quadratic reward function), an optimal solution will assign each student (who is willing to join at least one group) to exactly one group.

Each student can only be assigned to a group if they are willing to join it. For each group i, if it has a_i assigned students the cost incurred is \[ C_i \times a_i^2. \] The goal is to compute the minimum total reward payment required by the finance office when the number of participating students is maximized.

Input Format: The first line contains three integers: n, m, and k (the maximum number of groups a student can join). The second line contains m integers, where the i-th integer is \(C_i\), the reward coefficient for group i. This is followed by n lines. The j-th of these lines starts with an integer p_j indicating how many groups student j is willing to join, followed by p_j distinct integers (each between 1 and m inclusive) denoting the indices of the available groups for that student.

Output Format: Output a single integer, which is the minimum total reward payment the finance office must make under an assignment that maximizes the number of participating students.

Note: Even though each student is allowed to join at most k groups, to maximize the number of participating students it suffices to assign each student to exactly one group (if possible).

inputFormat

The input begins with a line containing three integers n, m and k separated by spaces.

The second line contains m integers: \(C_1, C_2, \ldots, C_m\), where \(C_i\) is the reward coefficient for group i (used in the formula \(C_i \times a^2\)).

Then follow n lines. The j-th line begins with an integer p_j, indicating the number of groups student j is willing to join, followed by p_j integers representing the indices (1-indexed) of the groups the student is willing to join.

outputFormat

Output a single integer: the minimum total reward payment made by the finance office in an assignment that maximizes the number of participating students.

sample

3 2 1
1 2
1 1
2 1 2
1 2

6