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 BSC(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*M grid. In each N number of rows, there will be M 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 T (≤ 100), denoting the number of test cases. In the first line of each test case, you will be given two integers N (1≤N≤100) and M(0≤M≤100). In the next N lines you will be given M space separated cells which will contain either 0 or 1. 1 means there is a bubble in this cell and 0 means there is an obstacle in this cell. In the last line of test case you will be given two integer B(0≤B≤100) and W(0≤W≤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