Dark Moments Solution

Dark Moments

Prepbuddy is fond of traveling via trains. So he planned a journey to prepland and he is traveling by train right now. The train has NN cars, the length of the ithith car is AiAi meters. Let us ignore the distance between the cars.

Prepbuddy noticed that some cars have the light on, while some have the light off. The train is approaching a tunnel that has a length of HH meters. Prepbuddy actually doesn’t want a moment when all the cars inside the tunnel have lights off. Prepbuddy calls such a moment a dark moment if all cars that have some non-zero length part in a tunnel have the light off. To avoid dark moments, prepbuddy wants to turn the light on in some cars.

Help Prepbuddy to turn the light on in the minimal number of cars, that there was no dark moment while the train passes the tunnel.

Input Format

The first line contains an integer TT denoting the number of test cases. The first line of each test case contains two integers NN and HH, the number of cars, and the length of the tunnel. The second line contains NN integers AiAi the lengths of the cars. The third line contains n integers, the ithith of them is 11 if the ithith car initially has the light on, or 00 if it has the light off. Cars are described in the order they would enter the tunnel.

The sum of values of NN for all tests doesn’t exceed 106106.

Output Format

For each test case output one integer the minimal number of cars that Prepbuddy must turn the light on so that there was no dark moment.

Constraints

1≤T≤1001≤T≤100 1≤N≤1051≤N≤105 1≤H≤1091≤H≤109 1≤Ai≤1091≤Ai≤109

Time Limit

2 second

Example

Sample Input

2 7 10 5 3 4 5 9 9 9 1 0 0 0 1 0 0 5 2 1 2 3 1 1 1 1 0 1 1

Sample Output

2 1

Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.

JULY 2021 CODING MARATHON

Leave a Comment