REPROAD - Repair road


Vietnamese

Sau một trận động đất,

 nhiều con đường đã bị phá hủy. Mỗi con đường có một vài đoạn bị hư hỏng, nên phương tiện không thể di chuyển trên những đoạn đường này. Nhằm đảm bảo mạng lưới giao thông được thông suốt, chính phủ đã tiến hành sửa đường. Với mỗi đơn vị đường (1 block), chính phủ cần sử dụng 1 đơn vị tiền. Nếu con đường có M đoạn bị hỏng, thì chính phủ sẽ cần M đơn vị tiền. Tuy nhiên, có quá nhiều đoạn đường bị hỏng trong khi chính phủ chỉ có K đơn vị tiền dành cho việc sửa đường. Vậy với K đơn vị tiền, chính phủ muốn sửa con đường sao cho số đoạn đường liên tiếp mà phương tiện giao thông có thể di chuyển là lớn nhất.

Ví dụ, hình ảnh dưới đây minh họa 1 con đường với 11 đoạn, chúng có 4 đoạn bị hỏng được đánh dấu bằng các ô màu xám (đoạn 2, 3, 6 và 8).

Nếu họ chỉ có 2 đơn vị tiền cho việc sửa đường, để thu được đoạn đường liên tiếp dài nhất cho phương tiện giao thông di chuyển, chính phủ phải sửa 2 đoạn 6 và 8, khi đó phương tiện có thể di chuyển giữa đoạn 4 và 11, với độ dài đoạn đường là 8.

Cho trước trạng thái của 1 con đường, hãy in ra chiều dài lớn nhất của đoạn đường liên tiếp mà phương tiện giao thông có thể di chuyển sau khi sửa đường sử dụng K đơn vị tiền. Đáp án cho ví dụ nêu trên là 8.

Input

Tổng số lượng phép thử là T (1 <= T  <= 20) được cho trên dòng đầu tiên.

Mỗi phép thử được cho trên 2 dòng, dòng đầu tiên của mỗi phép thử là số lượng đoạn đường N (5 <= N <= 10000) của con đường và số tiền dành cho việc sửa đường K (0 <= K <= N), cách nhau bởi 1 dấu cách trắng. Dòng tiếp theo mô tả trạng thái của con đường, những đoạn bị hỏng có giá trị là '0' và những đoạn không bị hỏng là '1'. Các giá trị trên cùng 1 dòng được ngăn cách bởi 1 dấu cách trắng.

Output

Hãy in đáp án của mỗi phép thử trên 1 dòng. 

Sample

Input

Output

2

10 1

1 1 1 1 1 1 0 0 1 1

11 2

1 0 0 1 1 0 1 0 1 1 1

7

8


English

After the earthquake, many road were damaged. Each road has some blocks were damaged, so vehicles cannot move on these blocks. To ensure the traffic network is connected, they need to repair those roads. For each road, to repair 1 block, they need 1 unit of money. So if a road has M blocks are damaged, then they need M unit of money. However, too many roads were damaged, they only have K unit of money to repair a specific road. Then with K unit of money, they wish to repair the road such that the number of consecutive blocks that vehicles can move on is maximum.

For example, the following is a road with 11 blocks, there are 4 blocks need to repair are marked in gray color (block 2, 3, 6 and 8).

If they have only 2 unit of money to repair this road, to get maximum the number of consecutive blocks that vehicles can move on after repair, they must to repair the block 6 and 8, then the vehicles can move from block 4 to block 11, and the length is 8.

 

Given a status of road, print out the maximum consecutive blocks that vehicles can move on after repair with maximum K unit of money. The answer for the above example should be 8.

Input

The total number of test cases T (1  T ) will be given the in the first line.

Each test case will be given in the following 2 lines, the first line of each test case is a number of blocks of the road N (5 <= N <= 10000) and a number K (0 <= K <= N) separated by a space. The next line is the status of road, those blocks were damaged are indicated with '0' and those not are indicated with '1'. Adjacent blocks in the same line are separated with a blank space.

Output

Print the answer for each test case on 1 line.


 

Sample

Input

Output

2

10 1

1 1 1 1 1 1 0 0 1 1

11 2

1 0 0 1 1 0 1 0 1 1 1

7

8

 


hide comments
sandeep_4141: 2017-06-15 22:20:30

sliding windows or two pointer made it easy !!
AC in one go !!

aronzx: 2017-04-28 21:22:37

My 100 AC :)

darko_maksimov: 2017-02-08 14:53:16

On submission i get:once runtime error (SIGSEGV) once wrong answer for the same code. Moreover on Ideone the code solves the problem. Any suggestion what is the problem?

uvshuvo: 2017-01-11 23:58:36

Help please...On submission it saying wrong answer...but code running successfully in ideone.....what to do????
@uvshuvo: bcz you didn't cover all cases.

Last edit: 2017-01-23 11:41:37
shreeshiv: 2017-01-11 17:05:42

limit of n and k is not given in english
@shreeshiv: thank you, I updated.

Last edit: 2017-01-23 11:40:31
Ishwar: 2016-11-26 16:40:10

some one help with different inputs and outputs

Ishwar: 2016-11-26 12:59:33

input consist of spaces??

Anonomous: 2016-10-07 10:16:50

Given N and K, a list of N elements consisting of only 1 and 0, what is the maximal length of continuous 1s you can get if you are to change exactly K 0s to 1s. First line of input is T, number of test cases, followed by N and K, followed by N elements of 1 and 0.

ravikc12: 2016-09-27 14:24:34

only if this was in English


Added by:yeguzi
Date:2016-03-18
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY