Bloblob is a very famous bubble shooter. He has a Rifle with an infinite number of bullets to shoot the bubble. Now this time Bubble Shooting Corporation is making this game little bit harder for him.This time Bloblob will be able to use a limited number of bullets.
This game will take place on a grid. In each of the number of rows, there will be cells. And in each cell, there can be a bubble or an obstacle.
Bloblob can shoot from either left side or right side of a row. At one time he can only target a particular row. He can't use more than one bullet for a particular row.
You are given maximum number of obstacle a bullet can pierce. You can assume that a bullet can pierce infinite number of bubble. You have to find out maximum number of bubble Bloblob can shoot.
Input starts with an integer (), denoting the number of test cases. In the first line of each test case, you will be given two integers () and (). In the next lines you will be given space separated cells which will contain either or . means there is a bubble in this cell and means there is an obstacle in this cell. In the last line of test case you will be given two integer () and () the maximum number of bullet Bloblob can use and maximum number of obstacle that a bullet can pierce.
For each case, print the case number and the maximum number of bubble Bloblob can shoot.
Input | Output |
---|---|
2 3 3 0 1 0 1 0 1 0 1 1 2 1 2 5 0 0 1 0 0 0 1 1 0 0 2 2 | Case 1: 4 Case 2: 3 |