Last Updated: 19 Mar, 2021
##### Busy Ninja
Moderate
Problem statement

#### Ninja is doing an offline course that has a duration of βNβ days. After attending the course, the ninja gains some experience βEXP[i]β (for the day βiβ). On some days, the ninja is busy and will not be able to attend the course, hence not gaining any experience on that day. If βBUSY[i] = 1β, then the ninja is busy on day βiβ. Otherwise, if βBUSY[i] = 0β, the ninja attends the course on day βiβ. To get the most out of the course, the ninja can focus for βKβ days straight (only once during the course), attending the course every day for these βKβ consecutive days. You are given two arrays, βEXPβ and βBUSYβ, each of size βNβ. You are also given an integer βKβ. The task is to find the maximum experience that the ninja can gain from this course.

##### Example :
``````βNβ = 6, βKβ = 3
βEXPβ = [1, 4, 2, 2, 3, 6]
βBUSYβ = [0, 1, 1, 0, 0, 1]
To get the maximum experience ninja has to focus on the last β3β days. The maximum experience gained will be = 1 + 2 + 3 + 6 = 12. So, the answer is 12.
``````
##### Input Format :
``````The first line of input contains an integer βTβ which denotes the number of test cases. Then, the βTβ test cases follow.

The first line of each test case contains two space-integer βNβ and βKβ denoting the course duration and the number of days ninja can focus on the course.

The second line of each test case contains βNβ space-separated integers representing the array βEXPβ.

The third line of each test case contains βNβ space-separated integers representing the array βBUSYβ.
``````
##### Output Format :
``````For every test case, print a single line containing a single integer denoting the maximum experience that the ninja can gain from this course.

The output of each test case will be printed in a separate line.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 100
1 <= N <= 1000
0 <= K <= N
0 <= EXP[i] <= 10 ^ 6
BUSY[i] = {0, 1}

Time limit: 1 second.
``````
Approaches

## 01Approach

Use βresβ to store the maximum experience that ninja can gain. Initially, ninja focuses on attending the first βKβ days starting from day β0β (to βK - 1β). Calculate the total experience gained and store it in βresβ. Now, focus on the next βKβ days starting from day β1β (to βKβ), and if the total experience gained is more than βresβ, then update βresβ. Similarly, find the experience gained for each such combination until the last βKβ days, each time updating the value of βresβ.

Find the experience gained without requiring any focus(non-busy days) and store it in βdirectExpβ.To find the experience gained after focusing on any βKβ days, iterate through the βKβ days and only add experiences of those days when ninja was busy to βdirectExpβ (as βdirectExpβ already stores the experience gained on non-busy days).

• Initialize βresβ to βINT_MINβ. Use βresβ to store the answer. βINT_MINβ  is the lowest possible integer value.
• Initialize βdirectExp = 0β. Use to store the experience gained on non-busy days.
• Run a loop where βiβ ranges from β0β to βn - 1β:
• If βBUSY[i]β is equal to 0, then:
• βdirectExp += EXP[i]β
• Run a loop where βiβ ranges from β0β to βN - Kβ:
• βcurExp = directExpβ. Use to find the experience gained from busy days if ninja focusses from the day βiβ to βi + K - 1β.
• Run a loop where βjβ ranges from βiβ to βi + K - 1β:
• If βBUSY[j]β is equal to 1, then:
• βcurExp += EXP[j]β
• If βcurExpβ is greater than βresβ, then:
• βres = curExpβ.
• Return βresβ as the answer.