E. Critical Perfect
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Fengmi is challenging a high-difficulty level in a music game. There are $$$n$$$ notes falling in order, and the $$$i$$$-th note has a base score $$$a_i$$$. When the player hits the first $$$i$$$ notes, the cumulative score $$$s_i = \sum_{k=1}^i a_k$$$ determines the trigger condition for the combo effect.

Specifically, the $$$i$$$-th note has a target interval $$$[l_i, r_i]$$$ for the cumulative score. Only if $$$s_i$$$ falls into this interval can the Critical Perfect combo effect performance be triggered; otherwise, the effect chain will be interrupted.

As the owner of the "Area Amplification" item, Fengmi can use this item any number of times. Each use allows her to select a contiguous segment of notes $$$[l, r]$$$ and increase the base score of each note in this segment by $$$1$$$. The number of uses affects the final level score, so Fengmi wants to achieve a Critical Perfect combo throughout the entire level with the minimum number of uses.

Please help her calculate the minimum number of times the Area Amplification item must be used so that for every note $$$i$$$, the cumulative score $$$s_i$$$ satisfies $$$l_i \le s_i \le r_i$$$, or report that no solution exists.

Input

There are multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 5000$$$), the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of notes.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the base score of each note.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^{18}$$$) — the target interval for the cumulative score after note $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output a single integer — the minimum number of item uses. If it is impossible, output $$$-1$$$.

Example
Input
2
3
6 2 8
8 16
16 32
28 36
2
0 0
1 1
0 0
Output
4
-1
Note

For the first test case in the sample, one feasible operation scheme is as follows: use the item $$$4$$$ times on the interval $$$[1,3]$$$. The original base score sequence becomes $$$[10,6,12]$$$, and the cumulative scores become $$$[10,16,28]$$$, which satisfies the conditions. The total number of operations is $$$4$$$. It can be proved that no scheme with fewer operations exists.

For the second test case in the sample, it can be proved that no feasible operation scheme exists.