Make the team

Interview

Time limit1sMemory limit1024 MB

Summary

Assign each video a distinct whole-hour start time so that the latest finish time is as early as possible.

Level: Medium5 of 10
Topics: Graph, Binary search
Solved: No attempts yet

Problem

You want to join the programming team, and you believe that watching several videos will improve your chances. Each video is one hour long and plays only at specific times. You want to finish watching all the videos as early as possible so you have more time to practice.

For example, suppose you want to watch two videos. The first video plays during $[1,2)$ , $[4,5)$ , $[8,9)$ , and $[12,13)$ . The second video plays during $[4,5)$ , $[7,8)$ , and $[11,12)$ . The earliest time you can finish both is 5. Watch the first video during $[1,2)$ and the second video during $[4,5)$ . Every video lasts exactly as long as one playback interval. You can watch back-to-back videos. If one video plays during $[x, x+1)$ and another plays during $[x+1, x+2)$ , where $x$ is a positive integer, you can watch both in sequence.

Given the times each video is available, find the earliest time you can finish watching all the videos. The videos can be watched in any order as long as the intervals allow it.

Input

The first line contains one integer $n$ ( $1 \le n \le 200$ ), the number of videos. Each of the next $n$ lines describes one video. The $i$ -th line starts with an integer $t_i$ ( $1 \le t_i \le 30$ ), the number of times video $i$ is available, followed by $t_i$ space-separated start times. The start times for each video form a strictly increasing list of positive integers, with a maximum value of 1000. It is guaranteed that at least one arrangement lets you watch all the videos.

Output

Print the earliest time at which you can finish watching all the videos.

Examples2

Example 1
Input
```
3
2 4 6
3 4 9 11
1 4
```
Expected output
```
10
```
Example 2
Input
```
4
2 3 11
3 2 9 11
2 2 3
2 3 9
```
Expected output
```
12
```