You have N rods with you. The i-th rod has a length of A_{i} and a beauty of B_{i}.

You'd like to arrange these rods side-by-side in some order on the number line, starting from 0.  

Let x_{i} be the starting position of the i-th rod in an arrangement. The beauty of this arrangement is

\sum_{i=1}^N x_{i}\cdot B_{i}

What is the maximum beauty you can attain?

Note that the left endpoint of the first rod you place must be 0, and you cannot leave any space between rods.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases.
- Each test case consists of three lines of input.
- The first line of each test case contains a single integer N, the number of rods.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}
- The third line of each test case contains N space-separated integers B_{1}, B_{2}, \ldots, B_{N}

------ Output Format ------ 

- For each test case print on a new line the answer: the maximum value of \sum_{i=1}^N x_{i} B_{i} if the order of rods is chosen optimally.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{4}$
$1 ≤ B_{i} ≤ 10^{4}$
- The sum of $N$ across all testcases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
2
2
1 2
4 6
4
2 8 9 11
25 27 100 45
----- Sample Output 1 ------ 
8
2960
----- explanation 1 ------ 
Test case $1$: Place the second rod followed by the first one. This makes $x_{2} = 0$ and $x_{1} = 2$, giving us a beauty of $2\cdot 4 + 0\cdot 6 = 8$, which is the maximum possible.

Test case $2$: Place the rods in the order $[2, 4, 3, 1]$. This gives us $x = [28, 0, 19, 8]$, and the beauty is $28\cdot 25 + 0\cdot 27 + 19\cdot 100 + 8\cdot 45 = 2960$.

Difficulty: HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
def f(x):
	return x[1]
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	l = list(map(int, input().split()))
	k = [[0 for x in range(2)] for y in range(n)]
	for i in range(n):
		k[i][0] = i
		k[i][1] = l[i] / p[i]
	k.sort(key=f)
	sum = 0
	z = 0
	for i in range(n):
		sum = sum + l[k[i][0]] * z
		z = z + p[k[i][0]]
	print(sum)


from functools import reduce
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append((a[i], b[i]))
	res = 0
	l = 0

	def compare(a):
		return a[0] / a[1]
	arr.sort(key=compare, reverse=True)
	for i in range(n - 1):
		l += arr[i][0]
		res += l * arr[i + 1][1]
	print(res)


def key(val):
	return val[1] / val[0]
T = int(input())
for t in range(T):
	n = int(input())
	s1 = input().split()
	leng = [int(x) for x in s1]
	s2 = input().split()
	beau = [int(x) for x in s2]
	arr = []
	tup_arr = zip(leng, beau)
	for (a, b) in tup_arr:
		arr.append([a, b])
	arr.sort(key=key)
	cost = 0
	c_length = 0
	for y in arr:
		cost += y[1] * c_length
		c_length += y[0]
	print(cost)


t = int(input())

def compare(a):
	return a[1] / a[0]
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = [(a[i], b[i]) for i in range(n)]
	arr.sort(key=compare)
	(prefix, ans) = (0, 0)
	for k in range(n):
		ans += prefix * arr[k][1]
		prefix += arr[k][0]
	print(ans)


def key(arr1):
	return arr1[1] / arr1[0]

def ans(n, length, beauty):
	arr = []
	for (y1, y2) in zip(length, beauty):
		arr.append([y1, y2])
	arr.sort(key=key)
	cost = 0
	c_length = 0
	for y in arr:
		cost += y[1] * c_length
		c_length += y[0]
	return cost
test_cases = int(input())
while test_cases != 0:
	d_ = int(input())
	d = list(map(int, input().split()))
	d2 = list(map(int, input().split()))
	print(ans(d_, d, d2))
	test_cases -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	o = []
	for i in range(n):
		o.append([b[i] / a[i], i])
	o.sort()
	m = 0
	x = 0
	for j in o:
		i = j[1]
		m += x * b[i]
		x += a[i]
	print(m)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append([a[i] / b[i], i])
	arr.sort(reverse=True)
	now = 0
	curent = 0
	for j in arr:
		now += curent * b[j[1]]
		curent += a[j[1]]
	print(now)
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = list(map(int, input().split()))
	pts = list(zip(l, b))
	pts = sorted(pts, key=lambda x: x[1] / x[0])
	currdist = 0
	res = 0
	for (i, j) in pts:
		res += currdist * j
		currdist += i
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	opt = [[b[i] / a[i], i] for i in range(n)]
	opt.sort()
	ans = 0
	x = 0
	for i in opt:
		id = i[1]
		ans += x * b[id]
		x += a[id]
	print(ans)


for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [(b[i] / a[i], i) for i in range(n)]
	c.sort()
	x = [0] * n
	s = 0
	for (z, i) in c:
		x[i] = s
		s += a[i]
	beauty = sum((x[i] * b[i] for i in range(n)))
	print(beauty)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	complist = []
	order = []
	for i in range(n):
		comp = a[i] / b[i]
		complist.append((comp, i))
	complist.sort(key=lambda complist: complist[0])
	for i in range(len(complist)):
		order.append(complist[i][1])
	order.reverse()
	ans = 0
	incr = 0
	for i in order:
		ans += b[i] * incr
		incr += a[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append([a[i] / b[i], i])
	arr.sort(reverse=True)
	ans = 0
	cur = 0
	for r in arr:
		ans += cur * b[r[1]]
		cur += a[r[1]]
	print(ans)


t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	s = 0
	d = {}
	for i in range(n):
		d[i] = a[i] / b[i]
	d = sorted(d, key=lambda x: d[x], reverse=True)
	offset = 0
	for i in d:
		s += offset * b[i]
		offset += a[i]
	print(s)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	br = list(map(int, input().split()))
	l = [[ar[i] / br[i], i] for i in range(n)]
	l.sort(reverse=True)
	(m, res) = (0, 0)
	for i in l:
		res += br[i[1]] * m
		m += ar[i[1]]
	print(res)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	ratio = [[A[i] / B[i], i] for i in range(n)]
	ratio.sort(reverse=True)
	length = 0
	ans = 0
	for r in ratio:
		ans += B[r[1]] * length
		length += A[r[1]]
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([a[i], b[i], a[i] / b[i]])
	l.sort(key=lambda x: x[2])
	l.reverse()
	s = 0
	ans = 0
	for i in range(n):
		ans += s * l[i][1]
		s += l[i][0]
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	order = sorted(range(n), key=lambda i: -a[i] / b[i])
	ans = 0
	curr = 0
	for i in range(n):
		ans += curr * b[order[i]]
		curr += a[order[i]]
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	b = list(map(int, input().split()))[:n]
	t = sorted(list(((i, b[i] / a[i]) for i in range(n))), key=lambda r: r[1])
	ans = 0
	s = 0
	for (i, f) in t:
		ans += s * b[i]
		s += a[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ind = [i for i in range(n)]
	ind.sort(key=lambda x: -a[x] / b[x])
	ans = prev = 0
	for i in ind:
		ans += b[i] * prev
		prev += a[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	t = sorted([(i, b[i] / a[i]) for i in range(n)], key=lambda r: r[1])
	res = 0
	s = 0
	for (i, frac) in t:
		res += s * b[i]
		s += a[i]
	print(res)


from sys import stdin, stdout
from heapq import heapify, heappop
from functools import cmp_to_key
stdint = lambda : int(stdin.readline())
seq = lambda : list(map(int, stdin.readline().strip().split()))

def compare(a, b):
	if a[0] * b[1] > a[1] * b[0]:
		return -1
	else:
		return 1
for _ in range(stdint()):
	n = stdint()
	first = seq()
	second = seq()
	arr = []
	for i in range(n):
		arr.append((first[i], second[i]))
	arr = sorted(arr, key=cmp_to_key(compare))
	l = arr[0][0]
	ans = 0
	for i in range(1, n):
		ans += l * arr[i][1]
		l += arr[i][0]
	print(ans)


import sys
from collections import defaultdict as dd, deque
input = lambda : sys.stdin.readline().strip()

def ii():
	return int(input())

def ia():
	return list(map(int, input().split()))
INF = float('inf')
MOD = 10 ** 9 + 7
for _ in range(ii()):
	n = ii()
	a = ia()
	b = ia()
	c = list(zip(a, b))
	c.sort(key=lambda x: x[1] / x[0])
	res = 0
	s = 0
	for (i, j) in c:
		res += s * j
		s += i
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	t = sorted([(i, b[i] / a[i]) for i in range(n)], key=lambda x: x[1])
	res = 0
	s = 0
	for (i, frac) in t:
		res += s * b[i]
		s += a[i]
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = {}
	for (ai, bi, i) in zip(a, b, range(n)):
		x[i] = ai / bi
	indexes = []
	for (k, v) in sorted(x.items(), key=lambda item: item[1], reverse=True):
		indexes.append(k)
	beau = []
	length = []
	running_sum = 0
	for i in indexes:
		beau.append(b[i])
		length.append(running_sum)
		running_sum += a[i]
	beauty = 0
	for (xi, bi) in zip(length, beau):
		beauty += xi * bi
	print(beauty)


from collections import defaultdict
import math as mt
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = list(map(int, input().split()))
	c = [list(i) for i in zip(a, b)]
	c.sort(key=lambda x: -(x[0] / x[1]))
	ans = 0
	curr = 0
	for i in range(n - 1):
		curr += c[i][0]
		ans += curr * c[i + 1][1]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	r = [0] * n
	for i in range(n):
		r[i] = b[i] / a[i]
	z = list(zip(r, a, b))
	z.sort()
	clen = 0
	ans = 0
	for i in range(n):
		ans += clen * z[i][2]
		clen += z[i][1]
	print(ans)


def solution(n, a, b):
	arr = []
	length = 0
	ans = 0
	for i in range(n):
		arr.append([a[i] / b[i], a[i], b[i]])
	arr.sort(reverse=True)
	for element in arr:
		ans += length * element[2]
		length += element[1]
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	b = list(map(int, input().split()))[:n]
	print(solution(n, a, b))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append((a[i] / b[i], a[i], b[i]))
	arr.sort(reverse=True)
	l = 0
	ans = 0
	for i in range(n):
		ans += l * arr[i][2]
		l += arr[i][1]
	print(ans)
	t -= 1


import functools

def soln(n, l, b):

	def sorted_by(a, b):
		if a[0] * b[1] > a[1] * b[0]:
			return -1
		elif a[0] * b[1] < a[1] * b[0]:
			return 1
		return 0
	cmp = functools.cmp_to_key(sorted_by)
	srr = sorted([(l[i], b[i]) for i in range(len(l))], key=cmp)
	res = 0
	x = 0
	for i in srr:
		res += i[1] * x
		x += i[0]
	return res
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(soln(n, l, b))


def musical_rods(n, rod_len, beauty):
	index = [i for i in range(n)]
	index.sort(key=lambda x: rod_len[x] / beauty[x], reverse=True)
	ans = prev = 0
	for i in index:
		ans += beauty[i] * prev
		prev += rod_len[i]
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	rl = [int(x) for x in input().split()]
	bi = [int(x) for x in input().split()]
	print(musical_rods(n, rl, bi))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = []
	for i in range(n):
		d.append([b[i] / l[i], i])
	e = sorted(d)
	x = 0
	y = 0
	for i in e:
		y += x * b[i[1]]
		x += l[i[1]]
	print(y)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	v = list(zip(a, b))
	v.sort(key=lambda x: -x[0] / x[1])
	s = 0
	sm = 0
	for e in v:
		sm += s * e[1]
		s += e[0]
	print(sm)


from sys import stdin

def Sort_Tuple(tup):
	tup.sort(key=lambda x: x[2])
	return tup

def finalList(weights, values, n):
	fli = list()
	for i in range(n):
		fli.append((weights[i], values[i], values[i] / weights[i]))
	Sort_Tuple(fli)
	return fli

def musicalRods(fli):
	start = 0
	ans = 0
	for i in fli:
		ans += i[1] * start
		start += i[0]
	return ans

def takeInput():
	n = int(input())
	if n == 0:
		return (list(), list(), n, 0)
	weights = list(map(int, input().split(' ')))
	values = list(map(int, input().split(' ')))
	maxWeight = sum(weights)
	return (weights, values, n, maxWeight)
t = int(input())
while t:
	(weights, values, n, maxWeight) = takeInput()
	fli = finalList(weights, values, n)
	ans = musicalRods(fli)
	print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ratios = [(a[i] / b[i], i) for i in range(n)]
	ratios.sort()
	total = 0
	length = sum(a)
	for r in ratios:
		length -= a[r[1]]
		total += b[r[1]] * length
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	l = []
	for k in range(n):
		l.append([a[k] / b[k], k])
	l.sort()
	l = l[::-1]
	q = 0
	s = 0
	for j in l:
		s += q * b[j[1]]
		q += a[j[1]]
	print(s)


import bisect
import math
import sys
from collections import Counter, deque
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	b = [int(i) for i in sys.stdin.readline().split()]
	l = list(zip(a, b))
	l.sort(key=lambda x: x[0] / x[1], reverse=True)
	c = l[0][0]
	ans = 0
	for i in range(1, n):
		ans += l[i][1] * c
		c += l[i][0]
	print(ans)


from sys import stdin
input = stdin.readline

def solve(N, A, B):
	C = [(a, b, b / a) for (a, b) in zip(A, B)]
	C = sorted(C, key=lambda x: x[2])
	count = 0
	x = 0
	for (a, b, c) in C:
		count += x * b
		x += a
	return count
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	B = [int(x) for x in input().strip().split()]
	print(solve(N, A, B))


import math
from collections import Counter

def li():
	return list(map(int, input().split()))

def n():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L
for _ in range(int(input())):
	size = n()
	A = li()
	B = li()
	Z = list(zip(A, B))
	Z.sort(key=lambda x: x[1] / x[0])
	ans = 0
	cur = 0
	for (x, y) in Z:
		ans += cur * y
		cur += x
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	leng = list(map(int, input().split()))
	val = list(map(int, input().split()))
	l = [[] for i in range(n)]
	for i in range(n):
		l[i].append(leng[i] / val[i])
		l[i].append(val[i])
		l[i].append(leng[i])
	l.sort(reverse=True)
	w = 0
	ans = 0
	for i in range(n):
		ans += w * l[i][1]
		w += l[i][2]
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	ans = [[cost[i] / a[i], i] for i in range(n)]
	ans.sort(key=lambda x: x[0])
	sol = 0
	x = 0
	for i in range(n):
		sol += x * cost[ans[i][1]]
		x += a[ans[i][1]]
	print(sol)


gtt = int(input())
for i in range(gtt):
	nn = int(input())
	aa = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(nn):
		l.append([aa[i], b[i], b[i] / aa[i]])
	l.sort(key=lambda x: x[2])
	d = 0
	ans = 0
	for x in l:
		ans += d * x[1]
		d += x[0]
	print(ans)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = [(b[i] / a[i], (a[i], b[i])) for i in range(n)]
	ans.sort()
	x = 0
	sum = 0
	for i in range(n):
		sum += x * ans[i][1][1]
		x = x + ans[i][1][0]
	print(sum)
	t -= 1


for temp in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	res = [b[i] / a[i] for i in range(n)]
	(res, a, b) = (list(t) for t in zip(*sorted(zip(res, a, b))))
	s = 0
	ans = 0
	for i in range(1, n):
		s += a[i - 1]
		ans += s * b[i]
	print(ans)


def last(n):
	return n[2]
t = int(input())
while t > 0:
	n = int(input())
	arr = []
	A = list(map(int, str(input()).split(' ')))
	B = list(map(int, str(input()).split(' ')))
	for i in range(n):
		arr.append((A[i], B[i], B[i] / A[i]))
	arr = sorted(arr, key=last)
	curr = 0
	ans = 0
	for i in range(n):
		ans = ans + curr * arr[i][1]
		curr = curr + arr[i][0]
	print(ans)
	t = t - 1


for x in range(int(input())):
	c = int(input())
	s = list(map(int, input().split()))
	d = list(map(int, input().split()))
	e = [[0, 0] for i in range(c)]
	for i in range(c):
		e[i][0] = s[i]
		e[i][1] = d[i]
	e.sort(key=lambda x: x[1] / x[0])
	cur = 0
	ans = 0
	for i in range(c):
		ans += e[i][1] * cur
		cur += e[i][0]
	print(ans)


def maximum_beauty(N, a, b):
	if N == 1:
		return 0
	else:
		mp = []
		for i in range(N):
			mp.append([b[i] / a[i], i])
		mp.sort()
		ans = tmp = 0
		for i in range(len(mp)):
			ans += b[mp[i][1]] * tmp
			tmp += a[mp[i][1]]
		return ans
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(maximum_beauty(N, A, B))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = [(a[i] / b[i], i) for i in range(n)]
	x = [0 for i in range(n)]
	d = sorted(d, key=lambda x: x[0])
	length = 0
	for i in range(n):
		ind = d[-1][1]
		x[ind] = length
		length += a[ind]
		d.pop()
	ans = 0
	for i in range(n):
		ans += b[i] * x[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	t = []
	for (i, j) in zip(A, B):
		t.append([j / i, i, j])
	t.sort(key=lambda x: x[0])
	d = 0
	s = 0
	for i in t:
		s += d * i[2]
		d += i[1]
	print(s)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(len(a)):
		c.append((b[i] / a[i], i))
	c.sort()
	x = 0
	ans = 0
	for i in c:
		ans += x * b[i[1]]
		x += a[i[1]]
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	p = []
	for i in range(n):
		p.append([x[i], y[i], y[i] / x[i]])
	p.sort(key=lambda x: x[2])
	(ans, c) = (0, p[0][0])
	for k in range(1, len(x)):
		ans += c * p[k][1]
		c += p[k][0]
	print(ans)


import sys
import math as m
from collections import Counter

def gcd(a, b):
	return b if a % b == 0 else gcd(b, a % b)

def li():
	return list(map(int, input().split()))

def print_l(l):
	return [i for i in l]

def si():
	return input()

def isKthBitSet(n, k):
	if n & 1 << k - 1:
		return True
	else:
		pass
	return False

def A():
	n = int(input())
	l = li()
	ct = 0
	for i in l:
		if i % 2 == 1:
			ct += 1
	if ct % 2 == 0:
		return 'YES'
	else:
		return 'NO'

def B():
	(n, x1, y1, x2, y2) = map(int, input().split())
	if x1 < 1 and y1 > n and (x2 < 1) and (y2 > n):
		return 0
	elif x1 < 1 or y1 > n:
		return min(min(n - x2 + 1, n - y2 + 1), min(x2, y2))
	elif x2 < 1 or y2 > n:
		return min(min(n - x1 + 1, n - y1 + 1), min(x1, y1))
	x = min(min(n - x1 + 1, n - y1 + 1), min(x1, y1))
	y = min(min(n - x2 + 1, n - y2 + 1), min(x2, y2))
	z = abs(x1 - x2) + abs(y1 - y2)
	return min(x + y, z)

def C():
	(n, k) = map(int, input().split())
	s = n * (n - 1) // 2
	if k < n // 2:
		x = n - 2 * k
		s -= x * (x - 1) // 2
	return s

def D():
	n = int(input())
	l1 = li()
	l2 = li()
	l = []
	for i in range(n):
		l.append([l2[i] / l1[i], l1[i], l2[i]])
	l = sorted(l)
	x = 0
	s = 0
	for i in range(n):
		s += x * l[i][2]
		x += +l[i][1]
	return s
for _ in range(int(input())):
	print(D())


import sys
import math
from collections import defaultdict, Counter, OrderedDict
from itertools import permutations
from collections import deque
from decimal import Decimal
from fractions import Fraction
import heapq
import bisect
import functools
sys.setrecursionlimit(10 ** 5)

def sin():
	return int(sys.stdin.readline())

def array():
	return list(map(int, sys.stdin.readline().strip().split()))

def two():
	return map(int, sys.stdin.readline().strip().split())

def multiple():
	return [int(x) for x in sys.stdin.readline().split()]

def string():
	return sys.stdin.readline().strip()

def sqrt(x):
	(low, high) = (0, x)
	while low <= high:
		mid = (low + high) // 2
		if mid * mid <= x < (mid + 1) * (mid + 1):
			return mid
		elif x < mid * mid:
			high = mid - 1
		else:
			low = mid + 1
t = sin()
for _ in range(t):
	n = sin()
	a = array()
	b = array()
	res = []
	for i in range(n):
		res.append([a[i], b[i], b[i] / a[i]])
	res.sort(key=lambda x: x[2])
	ans = 0
	x = 0
	for i in range(n):
		ans += x * res[i][1]
		x += res[i][0]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = [[0, 0] for i in range(n)]
	for i in range(n):
		x[i][0] = a[i]
		x[i][1] = b[i]
	x.sort(key=lambda x: x[1] / x[0])
	cur = 0
	ans = 0
	for i in range(n):
		ans += x[i][1] * cur
		cur += x[i][0]
	print(ans)


def maincase():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append((a[i], b[i]))
	l.sort(key=lambda x: x[1] / x[0])
	counter = 0
	sum1 = 0
	for i in l:
		sum1 += counter * i[1]
		counter += i[0]
	print(sum1)
for test in range(int(input())):
	maincase()


def solve():
	t = int(input())
	for i in range(t):
		n = int(input())
		length = list(map(int, input().split()))
		beaut = list(map(int, input().split()))
		arr = [0] * n
		for k in range(n):
			arr[k] = beaut[k] / length[k]
		list1 = arr
		list2 = length
		(list1, list2) = zip(*sorted(zip(list1, list2)))
		length = list2
		list1 = arr
		list2 = beaut
		(list1, list2) = zip(*sorted(zip(list1, list2)))
		beaut = list2
		x = 0
		tot_sum = 0
		for s in range(n):
			tot_sum += x * beaut[s]
			x += length[s]
		print(tot_sum)
solve()


for i in range(int(input())):
	n = int(input())
	le = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([le[i], b[i], b[i] / le[i]])
	l.sort(key=lambda x: x[2])
	s = l[0][0]
	count = 0
	for i in range(1, n):
		count += s * l[i][1]
		s += l[i][0]
	print(count)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	order = [[q / p, p, q] for (p, q) in zip(a, b)]
	order.sort()
	ans = 0
	for j in range(n):
		if j == 0:
			prev = order[j][1]
		else:
			ans += order[j][2] * prev
			prev += order[j][1]
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ans = []
	for i in range(len(a)):
		ans.append(tuple([a[i], b[i], b[i] / a[i]]))
	ans.sort(key=lambda x: x[2])
	sum = ans[0][0]
	answer = 0
	for i in range(1, len(a)):
		answer += sum * ans[i][1]
		sum += ans[i][0]
	print(answer)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = []
	for i in range(n):
		d.append([i, b[i] / a[i]])
	d = sorted(d, key=lambda x: x[1])
	s = 0
	c = a[d[0][0]]
	for i in range(1, n):
		s += c * b[d[i][0]]
		c += a[d[i][0]]
	print(s)


def maintestcase():
	n = int(input())
	ai = list(map(int, input().split()))
	bi = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append((ai[i], bi[i]))
	l.sort(key=lambda x: x[1] / x[0])
	counter = 0
	s = 0
	for i in l:
		s += counter * i[1]
		counter += i[0]
	print(s)
for test in range(int(input())):
	maintestcase()


from functools import cmp_to_key

def compare(x, y):
	if x[1] * y[0] > x[0] * y[1]:
		return 1
	elif x[1] * y[0] < x[0] * y[1]:
		return -1
	else:
		return 0
t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		k = [c[i], b[i]]
		l.append(k)
	l.sort(key=cmp_to_key(compare))
	s = 0
	r = 0
	for i in l:
		s += r * i[1]
		r += i[0]
	print(s)


a = int(input())
for i in range(a):
	c = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	final = [[arr1[i], arr2[i], arr2[i] / arr1[i]] for i in range(c)]
	sol = sorted(final, key=lambda l: l[2], reverse=False)
	s = 0
	index = 0
	for i in range(len(sol)):
		s += sol[i][1] * index
		index += sol[i][0]
	print(s)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	v = []
	for i in range(n):
		v.append((A[i], B[i]))
	v.sort(key=lambda x: x[1] / x[0])
	start = 0
	ans = 0
	for i in v:
		ans += i[1] * start
		start += i[0]
	print(ans)


t = int(input())
for t0 in range(t):
	n = int(input())
	len_nums = list(map(int, input().split()))
	beauty_nums = list(map(int, input().split()))
	weights = [(i, beauty_nums[i] / len_nums[i]) for i in range(n)]
	weights = sorted(weights, key=lambda item: item[1])
	len_until_now = 0
	score = 0
	for i in range(n):
		rod_i = weights[i][0]
		score += beauty_nums[rod_i] * len_until_now
		len_until_now += len_nums[rod_i]
	print(score)


def sorter(x):
	return b[x] / a[x]
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = list(range(n))
	l.sort(key=sorter)
	sum_ = 0
	answer = 0
	for i in l:
		answer += b[i] * sum_
		sum_ += a[i]
	print(answer)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	hashy = [[arr[i], brr[i]] for i in range(n)]
	hashy.sort(key=lambda x: x[1] / x[0])
	ans = 0
	length = 0
	for i in range(n):
		ans += length * hashy[i][1]
		length += hashy[i][0]
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([h[i], b[i], b[i] / h[i]])
	l = sorted(l, key=lambda x: x[2])
	s = 0
	ht = 0
	for i in l:
		s += i[1] * ht
		ht += i[0]
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	b = list(map(int, input().strip().split(' ')))
	temp = []
	for i in range(n):
		temp.append((a[i] / b[i], a[i], b[i]))
	temp = sorted(temp, reverse=True)
	ans = 0
	length = 0
	for i in temp:
		ans += length * i[2]
		length += i[1]
	print(ans)


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	aa = []
	ans = 0
	if 'codechef' == 28226329:
		print('Tanmay')
	a = A()
	b = A()
	for i in range(n):
		aa.append([a[i] / b[i], i])
	na = [0]
	aa.sort(key=lambda x: x[0], reverse=True)
	c = 0
	for i in range(1, n):
		c += a[aa[i - 1][1]]
		na.append(c)
	for i in range(n):
		ans += na[i] * b[aa[i][1]]
	print(ans)


for T in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	div = [b[i] / a[i] for i in range(n)]
	z = sorted(zip(div, a, b), reverse=False)
	current_length = 0
	res = 0
	for rod in z:
		res += current_length * rod[2]
		current_length += rod[1]
	print(res)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	info = []
	for i in range(n):
		info.append([b[i] / a[i], a[i], b[i]])
	info.sort()
	ans = 0
	l = 0
	for i in range(n):
		ans += l * info[i][2]
		l += info[i][1]
	print(ans)
	t -= 1


def sortSecond(elem):
	return elem[1]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	r = []
	for i in range(n):
		c = (i, b[i] / a[i])
		r.append(c)
	r.sort(key=sortSecond)
	x = 0
	ans = 0
	for i in range(n):
		ans += x * b[r[i][0]]
		x += a[r[i][0]]
	print(ans)