3438：ACM Training

FZU ACM team launched a series of training courses recently. The training courses lasts exactly N continuous days. There are M lecturers and each day there may be some lecturers talking abort different topics at different time. Each lecturer has a fixed time to make a lecture and the order of the lecturer is fixed. The following is a sample schedule (for example, the first record in the second rows means that daxia has to give a lecture at day 1,4,5 and On “Day 1” there are 4 lecturers making a lecture: daxia at class 1,AekdyCoin at class 4,bluewind at class 6,forza at class 7): The training courses are very popular and there are a lot people want to attend the courses. So being the manager of the courses, LL wants to repeat the training courses S times. But as you know, our lecturers are very busy and they want the training finish as early as possible. So could you write a program to calculate the minimum days it needs to finish all the training?Here is a simple example to help you understand the problem:There are two lecturers (daxia and yayamao), and the training courses last exactly 2 days.
Now suppose S=2, then one possible schedule may be (Note that schedule here is for all training courses, so here Day 3 is the first day of the second training, i.e.Day 3 is the “Day 1” of second training):It cost 4 days in total. But we can do it better, we can rearrange the courses as following: Now it only cost 3 days and it’s the best schedule we can achieve.

In the first line there is an integer T, indicates the number of test cases.(T<=100)
In each case, there is one line contains three integer numbers M,N,S(1<=M<=20, 1<=N<=8,1<=S<=10^6) , indicating the number of the lecturers, the total days of the training course and the repeating times of the training courses. Then following M lines, each line contains N integers of ‘0’ or ‘1’. If the j-th integer is "1" at the i-th line, it means lecturer i should make a lecture on day j.There will be at least one ‘1’ in each case.You should note that the order of the lecturers and the time interval between each lectures should not be changed in each training.
There may be some blank lines between each cases.

For each test case , output “Case d: “ first where d is the case number counted from one, then output the minimum days it need to finish all the training.