NARHIL - NARUTO AND HILLS


There are n hills in Konohagakure, the Hidden Village of the Land of Fire.

Naruto is standing on the peak of 1st hill and wants to see the peak of the nth hill. He can see the peak of hills ahead of him which have a height smaller than or equal to the one he is standing on, up to the next strictly taller hill. Naruto has the ability to jump from one hill to another. He can also use his chakra to cut a hill and reduce its height.

You are given two arrays A and H. Array H represents the height of hills.

The energy used in jumping from ith hill to jth hill is 2 times the absolute difference of A[i] and A[j]. If Naruto is standing on ith hill, he can cut any hill from (i+1)th to nth which has a height greater than ith hill. He can only reduce the height of a hill up to the height of ith hill. The energy used in cutting jth (i < j ≤ n) hill the absolute difference of H[i] and H[j].

You have to tell the minimum energy which will be used in order for Naruto to see the nth hill.

Note : Naruto can’t jump on the nth hill nor can he cut the nth hill.

Constraints

1 ≤ t ≤ 20

2 ≤ n ≤ 105

1 ≤ A[i] ≤ 100000

1 ≤ H[i] ≤ 100000

Input

  1. The first line of the input contains a single integer t denoting the number of test cases. The description of t test cases follows.
  2. The first line of each test case contains a single integer n denoting the number of hills.
  3. The second line contains n space-separated integers A1, A2, A3 ... An.
  4. The third line contain n space-separated integers H1, H2, H3 ... Hn representing the height of ith hill.

Output

Your program should print one line of output for each test case.Output minimum energy which will be used in order for Naruto to see the nth hill. If it is not possible for Naruto to see the peak of nth hill then output -1.

Example

Input: 3 5 1 7 6 12 8 2 9 4 3 1 7 3 8 6 7 19 18 9 1 3 5 2 10 4 5 6 2 7 4 5 9 3 1 2 3 4 5 6 Output: 10 11 -1

Explanation:

Test case 1: Naruto can jump to 3rd hill from where he can see the peak of 5th hill. Energy= 2 * |1-6| = 10.

OR

Naruto can cut 2nd, 3rd, and 4th hill without jumping anywhere. Energy = |2-9| + |2-4| + |2-3| = 10.

Test case 3: Naruto cannot see the peak of 6th hill whatever he may do.


hide comments
DOT: 2018-08-22 09:05:48

AC after too many TLEs. Used square root decomposition but had to tweak the block sizes and made adjustments in order to fit in the time limit. Great question too. Can anyone provide hints on a faster solution?

amit_redoc: 2018-06-25 14:04:08

being a die hard fan of naruto..........i loved jumping over the hills......finally learnt some fine jutsu......great concept!!!!

be1035016: 2018-06-25 11:03:24

good job launda_sr ;) btate hain:)
my 200th.Had to be this one

Last edit: 2018-06-25 11:09:13
a2j007: 2018-06-25 09:52:19

ak07 pro ! :D


Added by:ak07
Date:2018-06-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own