jal-mahal-lake

Jal Mahal Lake is famous tourist place in Jaipur. The lake has floating planks in a straight line. The planks are currently not attached to each other, and there may be gaps between some of them. You have to push them all together and connect them into a single long plank.

You are given the positions and lengths. For each valid i, there is a plank that is lengths[i] meters long and starts positions[i] meters from the beginning of the Tourist site of lake. (In other words, the coordinates currently occupied by this plank are in the interval from positions[i] to positions[i]+lengths[i].)

Moving a single plank one meter in either direction costs one unit of energy. Compute the smallest total amount of energy sufficient to push all planks together. In the final configuration the planks must be located one after another with no gaps between them.

(Note that there is no restriction on the movement of planks or on the final position of the single long plank. You may push the cars in any order, and he may even push some planks by a non-integer number of meters if he wants to.)

Input :

First line of input contains number of test cases T
Each test case contains three lines of input containing space separated integers.
First line of each test case, contains an integer N, denoting number of planks.
Next line contains N space separated integers, which is the position of N planks on x co-ordinate.
Next line contains again N separated integers denoting the lengths of the N planks.

Output :

Print the minimum energy required on a line for each test case.

Constraints :
1 ≤ T ≤ 10
2 ≤ Total Number of Planks ≤ 50
1 ≤ Length[i], Position[i] ≤ 10^9
Planks cannot overlap each other

SAMPLE INPUT
2
4
1 3 10 20
2 2 5 3
3
100 50 1
10 2 1

SAMPLE OUTPUT
15
96

Explanation

Test Case #1:

There are four planks. The intervals currently occupied by the planks are (1,3), (3,5), (10,15), and (20,23). In one optimal solution you would move each of the first two planks three meters to the right, the third plank two meters to the left, and the fourth plank seven meters to the left. At the end, the planks occupy the intervals (4,6), (6,8), (8,13), and (13,16). Total energy spent: 3+3+2+7 = 15.

Test Case #2;

There are three planks. The gaps between consecutive planks have 48 meters each. The best solution is to keep the middle plank in place and to push the other two towards it. This requires 48+48 = 96 units of energy.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t=eval(input())
for i in range(0,t):
	n=eval(input())
	pos=input()
	leng=input()
	pos=pos.split()
	leng=leng.split()
	pos=list(map(int,pos))
	leng=list(map(int,leng))
	diff=[]
	adiff=[]
	for j in range(0,n):
		diff.append([pos[j],leng[j]])
	diff.sort()
	#print diff
	for j in range(0,n-1):
		#print diff[j+1][0]
		#print diff[j][0]
		#print diff[j][1]
		x=diff[j+1][0]-(diff[j][0]+diff[j][1])
		#print "x="+str(x)
		adiff.append(x)
	
	#print adiff
	
   
	for j in range(0,n-1):
		c=j
		
		temp=adiff[:]
		#print temp
		z=j-2
		y=j+1
		while z>=0:
			temp[z]=temp[z]+temp[z+1]
			#print "z="+`z`
			#print "c="+`temp[z]`
			z-=1
		while y<(n-1):
			temp[y]=temp[y]+temp[y-1]
			#print "y="+`y`
			#print "c="+`temp[y]`
			y+=1
		#print temp    
		c=sum(temp)
		del temp
		#print "c="+`c`
		if j==0:
			minimum=c
		if c<minimum:
			minimum=c
		#temp=adiff    
	print(minimum)