Somewhere in the world, there is a lazy programmer Batyr. He recently started a new job and wants to make a work plan for the next N days. On the i-th day, Batyr gets new bi tasks that need to be completed.
The company has a regular release etiquette, so all tasks that Batyr receives on the i-th day must be completed no later than day min(N,i+D−1) for a known integer D.
Batyr calculated that if he focuses and works on the i-th day, he can complete ai tasks on that day, but no more. Alternatively, if Batyr decides not to work on the i-th day, he will not complete any tasks on that day. It should be noted that on the i-th day, Batyr can only perform tasks from days j≤i.
Although Batyr is a lazy programmer, he is honest. Therefore, he must complete all his tasks. What is the minimum number of days Batyr needs to work in order to complete all his tasks?
Input:
The first line contains a single integer t — the number of test cases.
The first line of each test case contains two integers N and D(1≤D≤N≤5⋅105).
The second line of the test case contains N integers a1,a2,…,aN(0≤ai≤109) — the maximum number of tasks Batyr can complete on the i-th day.
The third line of the test case contains N integers b1,b2,…,bN(0≤bi≤109) — the number of new tasks appearing on the i-th day.
It is guaranteed that the sum of N over all test cases does not exceed 5⋅105.
Output:
For each test case, output a single integer — the minimum number of days Batyr needs to complete all tasks. If this is not possible, output −1.