Evacuation to the Moon

Due to the rapid consumption of natural resources, it is predicted that Earth will soon become uninhabitable after the year 2300. To save humanity, a new habitat has been set up on the Moon. However, in the winter of 2177, a chain reaction of environmental collapses on Earth forces everyone to evacuate in the shortest possible time.

There are n intermediate stations located between Earth and the Moon. Additionally, there are m public transit spaceships operating on cyclic routes between these stations. All people initially are located on Earth, and every spaceship is initially at the first stop of its cyclic route. The spaceships have limited capacities: the i-th spaceship can carry at most \(h_i\) people at any given ride. Each spaceship follows a cyclic route. For example, a route expressed as (0, 1, 4) implies that the spaceship will visit Earth (represented by 0), an intermediate station 1, and the Moon (represented by n+1 which in this example is 4) repeatedly: 0 1 4 0 1 4 ....

The travel time between any two consecutive stops is exactly 1 unit. Passengers can only board or alight a spaceship when it is docked at a station (or Earth/Moon). Design an algorithm to plan a transportation scheme that transfers all \(p\) people from Earth (node 0) to the Moon (node \(n+1\)) in the minimum possible time under the capacity and scheduling constraints.

Note: The intermediate stations are numbered from 1 to \(n\). Earth is always represented by 0, and the Moon is represented by \(n+1\> in the input.

inputFormat

The first line contains three integers: \(p\) (the number of people), \(n\) (the number of intermediate stations), and \(m\) (the number of spaceships).

 p n m

Then \(m\) lines follow. Each line describes a spaceship. Each spaceship description starts with two integers: \(h_i\) (the capacity of the spaceship) and \(l_i\) (the number of stops in its cyclic route). This is followed by \(l_i\) integers, which represent the stops in order. The stops are nodes from the set {0, 1, 2, ..., n+1} where 0 represents Earth and \(n+1\) represents the Moon.

It is guaranteed that each spaceship will operate in a cyclic fashion. For example, if a spaceship's route is given as 0 1 4, then its sequence of stops will be 0 1 4 0 1 4 … and so on.

outputFormat

Output a single integer representing the minimum time required to transfer all \(p\) people from Earth (node 0) to the Moon (node \(n+1\)).

sample

10 2 1
5 4 0 1 2 3

7