I. Smuggling Cereal
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas and his army of red pandas are on a plane, attempting to smuggle a load of stolen cereal.

There are $$$n$$$ red pandas standing in a line on the plane, numbered $$$1, 2, \ldots, n$$$, and $$$n$$$ cereal boxes, also numbered $$$1, 2, \ldots, n$$$. The $$$i$$$-th red panda is currently standing in front of the $$$i$$$-th box.

The $$$i$$$-th red panda has a strength $$$a_i$$$. The $$$j$$$-th box has a weight $$$w_j$$$.

You want to push all the boxes off the plane. To accomplish this, you are allowed to perform the following operation.

  • Choose some $$$1 \le l \le r \le n$$$, such that all the following hold:
    1. For all $$$l \le i \le r$$$, there is exactly one box at position $$$i$$$.
    2. Either there is no box at position $$$l - 1$$$, or $$$l = 1$$$.
    3. The sum of weights $$$w_l + w_{l + 1} + \ldots + w_{r-1} + w_r$$$ does not exceed $$$a_r$$$.
  • The $$$r$$$-th red panda will push all boxes in the range $$$[l, r]$$$ to the left. In other words, for all $$$l \le i \le r$$$, the box at position $$$i$$$ will be moved to position $$$i-1$$$.

If a box is pushed from seat $$$1$$$, it will be pushed off the plane.

Help Thomas determine the minimum number of operations needed to push all boxes off the plane, or that it is impossible.

Input

The input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 1000$$$).

The first line of each test contains $$$n$$$ ($$$1 \le n \le 6000$$$).

The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$, the weights of the cereal boxes ($$$1 \le w_i \le 10^9$$$).

The third line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, the strengths of the red pandas ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$6000$$$.

Output

If it is impossible to push all boxes off, print -1.

Otherwise, print the minimum number of operations needed to push all boxes off the plane.

Example
Input
2
4
3 1 3 2
3 4 2 5
5
3 1 1 3 2
3 4 4 2 5
Output
7
11
Note

In the first sub-case, all boxes can be pushed off of the plane in 7 commands.

One way is as follows:

First, the $$$2$$$nd red panda pushes the range of boxes $$$[1,2]$$$.

Then, the $$$4$$$th red panda will push the range $$$[3,4]$$$.

The $$$2$$$nd red panda can then push the range $$$[1,2]$$$ again.

The $$$1$$$st red panda can push box $$$3$$$ off of the plane.

Then, the $$$3$$$rd, $$$2$$$nd, and $$$1$$$st red panda push box $$$4$$$ in that order.

Problem Credits: Ariel Shehter