Problem I
Olympic Swimming
Input: Standard Input

Output: Standard Output

 

Hurdles is a common event in athletics where the runners race in running tracks containing hurdles (obstacles). For the race some hurdles are placed evenly spaced along a straight running course. They are positioned so that they will fall over if bumped into by the runner.

 

The organizers of 20012 Olympic games are planning to introduce a hurdles event in swimming. For this purpose, some hurdles will be placed in the swimming pool used in the competition. Let's describe the construction of a swimming pool at first. A pool is L meters long & is divided into K equal size lanes across the width. Each participant swims along his own lane. As events of various length take place in the same pool, measurement of length is very critical. So, there is a mark after every meter along the length of the pool starting from 0 in one end. As it is said earlier, there are some hurdles placed in the pool. There is at most one hurdle in a lane between two adjacent length marks. Again, a hurdle will always be between two adjacent marks. Now, the hurdles are not uniformly distributed. For example, in a 5 meter long pool with 2 lanes, the first lane may have 2 hurdles, one between 1m & 2m while another between 3m & 4m. The second lane may have 1 hurdle, between 0m & 1m. For ensuring a fair race, the course must be defined in a way so that all the participants have to  face same number of hurdles. In other words, you are to select two length marks from the pool so that there are same number of hurdles placed in every lane between these two length marks. You can safely assume that, a race course will always start in a length mark.

 

Input

 

There is at most 60 test cases. The first line of every test case contains two integers, L (0<L<=50000) & K (1<=K<=30).  Each of the next K lines describes a lane. Each of these lines starts with an integer n (0<=n<=5000), the number of hurdles in that lane. Then follows n integers pi (1<=i<=n && 0<=pi<L). Each integer pi means there is a hurdle between length mark pi & pi  + 1.

 

The input is terminated with a case where L = K = 0.

 

Output

 

For each test case, print a single line containing “Case #X: Y meter(s)” where X is the case number  & Y is the longest race that can take place in that pool. The first test case is the one mentioned above.

 

Sample Input                              Output for Sample Input

5 2

2 1 3

1 0

5 3

3 0 3 4

2 0 3

2 3 4

0 0

Case #1: 3 meter(s)

Case #2: 3 meter(s)

 

Problemsetter: Mohammad Mahmudur Rahman

Special Thanks to: Md. Arifuzzaman Arif