Description

Due to humanity’s consumption of natural resources, people realized that around the year 2300, Earth would no longer be habitable. Therefore, new green zones were established on the Moon to enable migration when needed. Unexpectedly, in the winter of 2177, due to unknown reasons, Earth’s environment suffered a chain collapse, and humanity must migrate to the Moon as quickly as possible.

There are $n$ space stations located between Earth and the Moon, and there are $m$ public transport spacecraft shuttling back and forth among them. Each space station can hold an unlimited number of people, but each spacecraft has limited capacity: the $i$-th spacecraft can carry $h_i$ people. Each spacecraft periodically stops at a sequence of stations; for example, $(1,3,4)$ means the spacecraft will cyclically stop at stations $134134134\dots$. It takes time $1$ for a spacecraft to travel from any station to any other station. People can board or disembark only when a spacecraft is docked at a station (or the Moon, or Earth).

Initially, all people are on Earth, and all spacecraft are at their initial stops. Design an algorithm to find a transportation plan that transfers all people to the Moon in the shortest possible time.

Input Format

The first line contains three integers separated by spaces, representing the number of space stations $n$, the number of spacecraft $m$, and the number of people on Earth $k$.

Lines $2$ through $(m + 1)$ each describe one spacecraft. On line $(i + 1)$, the first integer $h_i$ is the capacity of the $i$-th spacecraft. Then an integer $r_i$ follows, representing the number of stops of the $i$-th spacecraft. After that are $r_i$ integers, in order, representing the indices of the stops $S_{i, j}$, where the space stations are numbered from $1$ to $n$, Earth is indexed as $0$, and the Moon as $-1$.

Output Format

Output a single integer representing the shortest time needed to transfer all people to the Moon. If there is no solution, output $0$.

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

5

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1 \leq n \leq 13$.
• $1 \leq m \leq 20$.
• $1 \leq k \leq 50$.
• $1 \leq r_i \leq n + 2$.
• $-1 \leq S_{i, j} \leq n$.

Translated by ChatGPT 5