You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.5 s

Memory Limit: 128.0 MB

Description

Roy is playing a game with a sequence of n positions, numbered from 1 to n. He starts at position 1 and wants to reach position n. Each position has:

• A value A[i] — the amount of money Roy collects at position i.
• A cost C[i] — the minimum total money required to enter position i.

Roy can move from position i to position j (i < j) if and only if the total money collected from positions i to j (inclusive) is at least C[j], i.e.:

A[i] + A[i+1] + ... + A[j] ≥ C[j]

Each valid move from one position to another takes exactly 1 second. Roy wants to maximize the total time (i.e., the number of valid moves) it takes him to reach position n.

You are given the arrays A and C. Determine the maximum number of valid moves Roy can make to reach position n, or print -1 if it is impossible to reach position n.

Format

Input

The first line contains a single integer T( 1 ≤ T ≤ \(10^4\) ) — the number of test cases.

For each test case:

• The first line contains a single integer n ( 1 ≤ n ≤ \(5 × 10^5\) ) — the number of positions.

• The second line contains n integers A[1], A[2], ..., A[n]. (- \(5 × 10^5\) ≤ A[i] ≤ \(5 × 10^5\))

• The third line contains n integers C[1], C[2], ..., C[n]. (- \(5 × 10^5\) ≤ C[i] ≤ \(5 × 10^5\))

• Sum of n overall test case doesn't exceed \(5 * 10^5\)

Output

For each test case, print a single integer — the maximum number of moves Roy can make to reach position n, or -1 if it is impossible.

Sample

5
1
-100
-50
2
1 1
3 -1
4
2 1 1 2
1 3 1 7
5
1 2 3 4 5
1 3 6 10 5
7
1 1 -1 -1 1 1 1
0 0 0 0 0 0 0

0
1
-1
2
4

Test case 1:
n=1, single position with A[1]=-100, C[1]=-50. Roy starts at 1, needs 0 moves. Output = 0.

Test case 2:
n=2, A=[1,1], C=[3,-1].

• To enter position 2 (j=2), sum from pos1 to 2 is 1+1=2, but C[2]=-1 ⇒ 2 ≥ -1 OK.
  So Roy can jump from 1→2 in 1 move. Output = 1.

Test case 3:
It's impossible to reach n.

Test case 4:
n=5, A=[1,2,3,4,5], C=[1,3,6,10,5].
possible path : 1→2->5
Maximum moves = 2.