Bus

A company runs one shuttle bus that takes employees home at the end of each day. To ride it, an employee registers online in advance. Every morning the company checks that the bus capacity is not exceeded and posts the list of riders for that day.

The rent of the bus is $p$ per day, and it does not depend on how many people ride. By a rule everyone accepted, exactly one of the people on the bus that day pays the whole rent to the driver. The name of the person who pays is announced daily as well.

Write a program that picks the person who pays on each day so that the assignment is fair in the sense defined below.

Let $L_1, L_2, \dots, L_d$ be the lists of employees on the bus on day 1 through day $d$, and let $n_i$ be the size of $L_i$. If an employee $A$ rides the bus on days $t_1, t_2, \dots, t_k$, the correct share of $A$ is

$P_A = p \left( \frac{1}{n_{t_1}} + \frac{1}{n_{t_2}} + \cdots + \frac{1}{n_{t_k}} \right)$

If $A$ is chosen to pay the rent $r$ times, $A$ actually pays $Q_A = r \times p$, which is $E_A = Q_A - P_A$ more than the correct share. The unfairness of an assignment is the maximum of $E_A$ over all employees $A$. An assignment with the smallest unfairness is a fair assignment.

The input holds several test cases. The first line of each test case has three positive integers $n$, $d$ and $p$, where $n$ is the number of employees, $d$ is the number of days, and $p$ is the daily rent of the bus ($n, d \le 500$, $p \le 10^9$).

The next $d$ lines describe one day each. Every such line starts with the number of employees on the bus that day, followed by that many employee IDs, each an integer between $1$ and $n$. No ID appears twice on the same line, and at least one employee rides on every day. To keep the arithmetic simple, $p$ is chosen so that the share of one employee is an integer on every day.

The last line of the input is 0 0 0 and must not be processed.

For each test case, print the unfairness of a fair assignment on its own line.