Make Equal Subarray
Problem Statement
You are given two arrays (A and B) each of size N.
You want to change A to B. Changing the i-th element of A to i-th element of B costs |Ai – Bi| that is, the absolute difference between two numbers.
You are also given an integer S denotes maximum cost.
Find the Maximum length of a subarray of A that can be changed to be the same as the corresponding subarray to B with the cost at most S (maximum cost).
The subarray of A is a contiguous part of the array A, i. e. the array Ai,Ai+1,…,Aj for some 1≤i≤j≤N.
Constraints
1 <= T <= 100 1 <= N <= 10000 1<= S <= 10^9 1 <= Ai, Bi<= 10^9
Input Format
The first line contains an integer T, the number of test cases. Then the test cases follow.
Each test case contains three lines of input.
First line will contain 2 space separated integers N and S.
Second line contains N space separated integers A1,A2,…,AN.
Third line contains N space separated integers B1,B2,…,BN.
Output Format
For each test case, output in a single line, the maximum length of a subarray.
Sample Input
2 5 6 1 2 3 4 5 4 5 2 4 2 4 10 4 5 2 6 7 5 2 4
Sample Output
3 4
Explanation of Sample
In the test case 1: subarray (2,3,4) of A can change to (5,2,4). With the cost 4, so the maximum length is 3.
In the test case 2: subarray (4,5,2,6) of A can change to (7,5,2,4). With the cost 5, so the maximum length is 4.