You are the owner of an ice cream parlour that opens for ‘N’ minutes in a day. Every minute, some number of customers enter the store, and each of them leaves after the end of that minute.
During some minutes of the day, you are very short-tempered and when you are short-tempered, the customers of that minute are not satisfied; otherwise, they are satisfied.
You know a secret technique to keep yourself calm for ‘X’ minutes straight. This secret technique can only be used once during the day.
A good shopkeeper doesn't want his customers to be unsatisfied, so you want to find the maximum number of customers that can be satisfied throughout the day.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains two single space-separated integers ‘N’ and ‘X’, respectively.
The second line of each test case contains ‘N’ single space-separated integers representing the number of customers that enter the bookstore on the i-th minute.
The third line of each test case contains ‘N’ single space-separated integers representing whether you are short-tempered on the i-th minute or not. If the value is 1, then you are short-tempered on that minute, and if it is 0, then you are not.
Output Format :
For each test case, the only line of output will print the maximum number of customers that can be satisfied throughout the day.
Print the output of each test case in a separate line.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= T <= 100
1 <= N <= 5000
1 <= X <= N
0 <= customers[i] <= 10^5
0 <= tempered[i] <= 1
Time limit: 1 sec
Sample Input 1 :
4 6 1 2 1 1
0 1 0 1 0 1
Sample output 1 :
Explanation of Sample output 1:
You keep yourself calm for the starting 2 minutes. The maximum number of customers that can be satisfied = 4 + 6 + 1 + 1 = 12.
Sample Input 2 :
5 2 0 1
1 1 1 1
1 2 4 0 1
0 0 0 0 0
Sample output 2 :