Teleport Pads

Time limit2sMemory limit512 MB

Summary

Each pad cycles through a fixed list of zones with its own period; find the earliest time Hyeonuk, starting on pad 1 at coordinate 0, can reach the exit zone by riding and switching pads.

Level: Hard8 of 10
Topics: Graph, BFS, Simulation, Number theory
Solved: No attempts yet

Problem

Hyeonuk, who won the International Cow Lineup Photo Contest, squandered his prize money on a trip and was caught by a witch. So that Hyeonuk could not run away, the witch built a huge labyrinth in front of her castle, and to escape her he must make his way through the labyrinth and reach its exit.

The labyrinth is a long line segment in one dimension, divided into zones at integer coordinates from 0 to 1,000,000. Between these zones are teleport pads, and each second every pad teleports to a different zone in the labyrinth. Anyone standing on a pad is teleported along with it. When two pads are in the same zone, Hyeonuk can switch to the other pad, and he is agile enough that switching takes no time. Because the gaps between zones are wide, he cannot cross to another zone by jumping without a pad.

Each pad has a teleport period: after its period elapses, it teleports back to its starting position, and the cycle repeats. Each pad does not appear in the same zone twice or more within its period. Also, the zones visited by two pads are all different except for at most one, and at most two pads visit any one zone.

The current time is 0 seconds, there are N pads in total, and Hyeonuk is standing on the first pad. The first pad is in the zone with coordinate 0 at time 0, and no other pad visits coordinate 0. At most one pad visits the zone containing the labyrinth's exit.

Hyeonuk must escape the labyrinth as fast as possible before the witch eats him. What is the minimum time for Hyeonuk to escape the labyrinth?

Input

The first line gives the number of pads N and the coordinate E of the zone containing the labyrinth's exit, separated by a space.

From the second line onward, the information for each pad is given. The information for the i-th pad consists of two lines. The first line gives the period Ki of the i-th pad, and the next line gives Ki coordinates. These coordinates are, in the order given, the coordinate at time 0, the coordinate at time 1, ..., the coordinate at time Ki-1.

Every coordinate is a nonnegative integer no greater than 106, and the coordinate of the first pad at time 0 is guaranteed to be 0. Also, no coordinate appears three or more times in the entire input.

Output

Print the minimum time for Hyeonuk to reach the zone containing the labyrinth's exit. If reaching it is impossible, print -1.

Constraints

1 ≤ N ≤ 100
1 ≤ Ki ≤ 4000

Hint

In samples 2, 3, and 4 the pads do not all have the same period, so they are not included in subtask 1.

Examples4

Example 1
Input
```
3 20
4
0 1 2 3
4
9 7 5 3
4
15 10 5 20
```
Expected output
```
7
```
Example 2
Input
```
2 3
3
0 1 2
2
3 2
```
Expected output
```
6
```
Example 3
Input
```
3 4
4
0 1 2 3
5
7 6 5 4 3
3
8 5 2
```
Expected output
```
8
```
Example 4
Input
```
2 4
4
0 1 2 3
2
3 4
```
Expected output
```
-1
```