F. Keys and Doors
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n+1$$$ rooms arranged in a line, numbered from $$$1$$$ to $$$n+1$$$ from left to right.

There are also $$$n$$$ doors numbered from $$$1$$$ to $$$n$$$, where the $$$i$$$-th door connects rooms $$$i$$$ and $$$i+1$$$.

Each door $$$i$$$ has an associated non-negative integer $$$a_i$$$.

For each $$$1 \le i \le n$$$, room $$$i$$$ initially contains $$$s_i$$$ keys.

At the beginning of the $$$0$$$-th second, you are in room $$$1$$$, and all doors are closed.

For each $$$k \ge 0$$$, the following events happen in order during the $$$k$$$-th second:

  • At the beginning of the $$$k$$$-th second, all doors $$$j$$$ such that $$$a_j = k$$$ open automatically.
  • Suppose you are currently in room $$$i$$$.
    • If you are not carrying a key and there is at least one key in room $$$i$$$, you may pick up one key from this room.
    • If you are carrying a key, you may drop it in room $$$i$$$.
  • At the end of the $$$k$$$-th second:
    • You may move to room $$$i+1$$$. If door $$$i$$$ is still closed, you must be carrying a key to move through it. The key will be consumed, and door $$$i$$$ will open.
    • You may move to room $$$i-1$$$ if $$$i \gt 1$$$.
    • You may stay in room $$$i$$$.

Any door, no matter how it was opened, remains open forever.

At any moment, you may carry at most one key.

During the process, multiple keys may be placed in the same room.

Your task is to find the minimum number of seconds required to reach room $$$n+1$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of doors.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the integers associated with the doors.

The third line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — the number of keys initially located in each room.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of seconds required to reach room $$$n+1$$$.

Example
Input
4
1
0
0
1
5
0
3
4 1 10
1 0 0
5
100 100 100 100 100
2 0 0 0 0
Output
1
6
7
103
Note

In the first test case, door $$$1$$$ opens automatically at the beginning of the $$$0$$$-th second. You can move to room $$$2$$$ at the end of the $$$0$$$-th second, so you reach room $$$2$$$ after $$$1$$$ second.

In the second test case, door $$$1$$$ opens automatically at the beginning of the $$$5$$$-th second. You can move to room $$$2$$$ at the end of the $$$5$$$-th second, so you reach room $$$2$$$ after $$$6$$$ seconds.

In the third test case, you can pick up the key in room $$$1$$$ and wait until door $$$1$$$ opens automatically at the beginning of the $$$4$$$-th second.

At the end of the $$$4$$$-th second, you move to room $$$2$$$, so you reach room $$$2$$$ after $$$5$$$ seconds.

Door $$$2$$$ has already opened automatically at the beginning of the $$$1$$$-st second, so you can move to room $$$3$$$ without using the key.

After that, you are in room $$$3$$$ after $$$6$$$ seconds, and you are still carrying the key. You can use it to open door $$$3$$$ and move to room $$$4$$$.

Therefore, you reach room $$$4$$$ after $$$7$$$ seconds.