Dudu is a very starving possum. He currently stands in the first shelf of a fridge. This fridge is composed of N shelves, and each shelf has a number Qi (1 ≤ i ≤ N) of food. The top shelf, where Dudu is, is identified by the number 1, and the lowest is identified by number N. Dudu doesn’t eat more than one food in the same shelf, because he doesn’t want to get noticed. Furthermore, Dudu is very fat and cannot climb the wall of the fridge to a shelf above — nobody knows how did he end up in the first shelf. Dudu is also afraid of height, so he is only able to climb down at most K shelves at a time (if he is at shelf i, he is only able to reach shelves i+1, i+2, ..., i+K). There is a chance Pj thathechoosestogetdownfromashelfitoashelfi+j(1≤j≤K). Ifhetriestogodowna number of shelves that makes him get past the lowest shelf, he gets out of the fridge — he will always get out of the fridge eventually, because someone left the door open. Each food of shelf i has a number of calories Ci,j that is absorbed by Dudu in case he eats it, and a probability Xi,j that it is chosen by Dudu, for j from 1 to Qi. Dudu starts his journey at shelf 1 and, when he is in a shelf, he will always choose a food to eat and then will go to another shelf. What is the expected number of calories that Dudu will absorb by the time he gets out of the fridge? Input The first line contains T (T ≤ 100) — the number of test cases, after this line T test cases follows. The first line of a test case contains two integers, N and K (1 ≤ N ≤ 500; 1 ≤ K ≤ 10) — the number of shelves in the fridge and the maximum number of shelves Dudu can climb down at a time, correspondingly. The second line of a test case contains K real numbers Pj, where Pj is the probability ∑ lines of a test case describes a shelf (from the shelf 1 to shelf N). Each line starts with a integer Qi (1 ≤ Qi ≤ 20), which is the amount of food existent is in this shelf. Qi pair follows, each pair containing ∑ 2realnumbersCi,j andXi,j (0≤Ci,j ≤100;0≤Xi,j ≤1; Output thatDudugoesdownjshelves,forjfrom1toK(0≤Pj ≤1; Kj=1Pj =1). EachofthenextN For each test case print a line containing ‘Case #X: Y ’, where X is the case number, starting at 1, and Y is the expected number of calories that Dudu will absorb by the time he gets out of the fridge. Y should be rounded up to 6 digits after the decimal point. Sample Input 2 21 1.0 2 50 0.5 100 0.5 2 10 0.5 20 0.5 52 0.3 0.7 5 10 0.2 20 0.3 5 0.1 25 0.35 2 0.05 2 20 0.4 40 0.6 1 4 1.0 3 30 0.8 3 0.1 4 0.1 10 1 0.1 2 0.1 3 0.1 4 0.1 5 0.1 6 0.1 7 0.1 8 0.1 9 0.1 10 0.1 Qi Xi,j =1). j=1
2/2 Sample Output Case #1: 90.000000 Case #2: 44.929950