Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bubble Shooter

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

Discussion

Statistics


92% Solution Ratio

IshrakEarliest, Nov '17

Fake_DeathFastest, 2441.7s

IshrakLightest, 131 kB

minhazmirazShortest, 910B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.