409656: GYM103660 I Array Division

Zhongli gives you two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. He asks you to divide $$$[1,2,\dots,n-1,n]$$$ into $$$k$$$ continuous subarrays(a division for index), each index $$$i$$$ belongs to exactly one subarray, and for these $$$k$$$ continuous subarrays you divided, each meets the condition $$$\sum a_i \ge \sum b_i$$$.

Formally, you should find $$$k$$$ pairs $$$[l_1, r_1], [l_2, r_2],\dots, [l_k, r_k]$$$ satisfying following conditions:

• $$$l_1=1, r_k=n$$$
• $$$l_i\le r_i$$$ for all $$$i\in [1, k]$$$
• $$$r_{i-1}+1=l_i$$$ for all $$$i\in [2, k]$$$
• $$$\sum\limits_{j=l_i}^{r_i} a_i \ge \sum\limits_{j=l_i}^{r_i} b_i$$$ for all $$$i\in [1, k]$$$

You should find the maximum $$$k$$$.

The first line contains a single integer $$$T(1\le T\le 5000)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n(1\le n\le 5000)$$$ — the length of two arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n(1\le a_i\le 10^9)$$$ — the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n(1\le b_i\le 10^9)$$$ — the array $$$b$$$.

It is guaranteed that $$$\sum n\le 5000$$$ over all test cases.

For each test case, output a single integer in a line — the maximum $$$k$$$, output $$$-1$$$ if there is no valid way to divide the two arrays.

3
5
1 2 3 4 5
2 2 2 2 2
3
1 2 2
2 2 2
3
1 1 4
2 2 2

3
-1
1