Bubble Shooter

MU Tech Fest Programming...
Limits 1s, 512 MB

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 N×MN \times M grid. In each of the NN number of rows, there will be MM 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

Input starts with an integer TT (0<T1000 < T \le 100), denoting the number of test cases. In the first line of each test case, you will be given two integers NN (1N1001 \le N \le 100) and MM (0M1000 \le M \le 100). In the next NN lines you will be given MM space separated cells which will contain either 00 or 11. 11 means there is a bubble in this cell and 00 means there is an obstacle in this cell. In the last line of test case you will be given two integer BB (0B1000 \le B \le 100) and WW (0W1000 \le W \le 100) the maximum number of bullet Bloblob can use and maximum number of obstacle that a bullet can pierce.

Output

For each case, print the case number and the maximum number of bubble Bloblob can shoot.

Sample

InputOutput
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

Submit

Login to submit.

Statistics

92% Solution Ratio
IshrakEarliest, Nov '17
Fake_DeathFastest, 2441.7s
IshrakLightest, 131 kB
minhazmirazShortest, 910B
Toph uses cookies. By continuing you agree to our Cookie Policy.