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 1^{st} hill and wants to see the peak of the n^{th} 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 i^{th} hill to j^{th} hill is 2 times the absolute difference of A[i] and A[j]. If Naruto is standing on i^{th} hill, he can cut any hill from (i+1)^{th }to n^{th} which has a height greater than i^{th} hill. He can only reduce the height of a hill upto the height of i^{th} hill. The energy used in cutting j^{th} (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 n^{th} hill.
Note : Naruto can’t jump on the n^{th} hill nor can he cut the n^{th }hill.
Constraints:
1 ≤ t ≤ 20
2 ≤ n ≤ 10^{5}
1 ≤ A[i] ≤ 100000
1 ≤ H[i] ≤ 100000
Input
 The first line of the input contains a single integer t denoting the number of test cases. The description of t test cases follows.
 The first line of each test case contains a single integer n denoting the number of hills.
 The second line contains n spaceseparated integers A_{1}, A_{2}, A_{3 },….. A_{n}.
 The third line contain n spaceseparated integers H_{1}, H_{2}, H_{3 },….. H_{n }representing the height of i^{th }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 n^{th} hill. If it is not possible for Naruto to see the peak of n^{th }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 3^{rd }hill from where he can see the peak of 5^{th} hill. Energy= 2*16=10.
OR
Naruto can cut 2^{nd},3^{rd},and 4^{th} hill without jumping anywhere.
Energy=29+24+23=10.
Test case 3 : Naruto cannot see the peak of 6^{th} hill whatever he may do.
hide comments
DOT:
20180822 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:
20180625 14:04:08
being a die hard fan of naruto..........i loved jumping over the hills......finally learnt some fine jutsu......great concept!!!! 

be1035016:
20180625 11:03:24
good job launda_sr ;) btate hain:)


a2j007:
20180625 09:52:19
ak07 pro ! :D 
Added by:  ak07 
Date:  20180624 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own 