I think most of you are familiar with the footnotes. They reside at the bottom of the page, describing various terms in that page. Some authors describe them as “Footnotes, the little dogs yapping at the heels of the text.” You are given an article of N lines, where some of which has keywords that need to be footnoted. Say, if you have the word “copotron” (Copotron: As described in science fiction novel “Copotronic Shukh Dukhkho (Aka Emotions)” by M. Zafar Iqbal, Copotron is the brain of a robot.) in pages 1, 3, 7 and 8, then all these 4 pages should have a footnote about “copotron”. Since, a page can have at most S lines, if you place Mi lines from the article in one page, you can place at most (S − Mi) numbers of footnotes at that page. Each page will have a number of consecutive lines, and if, the last line of page i is line b, then first line of page (i+1) will be line (b+1). Given the number of lines in the article, and the positions of the referenced words, find the minimum number of footnotes that has to be added. Input First line contains an integer T (1 ≤ T ≤ 35), the number of test cases. This is followed by three integers N (1 ≤ N ≤ 500), S (1 ≤ S ≤ 100) and W (0 ≤ W ≤ 100), the number of lines in the article, number of lines that can fit in a page and the number of keywords. Next W lines each describe the positions of each keyword. Each of these W lines starts with an integer Ki (1 ≤ Ki ≤ N), the frequency of keyword i, followed by Ki integers, the lines in the article, where they can be found. The line numbers will be between 1 and N. Output For each test case, output the case number, followed by the minimum number of footnotes to add. If it’s not possible to fit them, output ‘-1’. Description of the sample input/output In case 1: if you place two lines in the first page, and 3 on the second, then, first page will require 1 foot note for first keyword since it contains keyword 1 in lines 1 and 2, and 2nd page will require 2 footnotes for keywords 2 and 3, since they appear in lines 3,4 and 5. You can achieve similar result, if you place lines 1-2 on first page, 3-4 on second, and 5 on third page. In case 2: You can place at most 2 lines per page. There are 3 keywords, keyword 1 in lines 1 and 2, keyword 2 in lines 3 and 4, and keyword 3 in line 5. So, lines 1-5 each contain one keyword. We can fit at most two lines in a page. If we place 1 line in each page, then, we have to add 1 footnote as well. So, for 5 lines with keywords, we need 5 more footnotes. Please note that, it’s not possible to place 2 lines in any page, since, it would require 2 footnotes, and thus a total of 2 + 2 = 4 lines, which is more than S. In case 3: You can not place line 1 in any page, if you place it anywhere, there wont be any space available to place the footnote, since maximum number of lines per page is 1. Sample Input 3 553 212
2/2 234 15 523 212 234 15 111 11 Sample Output Case 1: 3 Case 2: 5 Case 3: -1