Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are $N$ cars (numbered $1$ through $N$) on a circular track with length $N$. For each $i$ ($2 ≤ i ≤ N$), the $i$-th of them is at a distance $i-1$ clockwise from car $1$, i.e. car $1$ needs to travel a distance $i-1$ clockwise to reach car $i$.

For each valid $i$, you can fill the $i$-th car's tank with up to $f_{i}$ litres of gasoline, with cost $c_{i}$ coins per litre.

After that, you choose some car, sit in this car and start driving in the clockwise direction. To move one unit of distance in this direction, you need to spend $1$ litre of gasoline. When you pass another car (even if you'd run out of gasoline exactly at that point), you steal all its gasoline. You cannot move if you do not have any gasoline left.

Your goal is to fill the cars in such a way that you are able to choose an optimal car, travel the clockwise distance $N$ and return to the place where you were initially. Under this constraint, you want to pay the least possible number of coins.

Find the smallest number of coins you need to pay. It is guaranteed that there is a way to travel the distance $N$. It can be proved that in such a case, the smallest number of coins is always an integer.

------  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$.
The second line contains $N$ space-separated integers $f_{1}, f_{2}, \ldots, f_{N}$.
The third line contains $N$ space-separated integers $c_{1}, c_{2}, \ldots, c_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest possible number of coins you need to pay.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 200,000$
$0 ≤ f_{i} ≤ 10^{9}$ for each valid $i$
$0 ≤ c_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 2,000$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
3

3

1 1 1

1 1 1

3

3 0 0

10 0 0

3

3 3 3

3 2 1
----- Sample Output 1 ------ 
3

30

3

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting


Solutions:
for _ in range(int(input())):
	N = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	traveled = total = 0
	f = list(list(zip(*sorted(zip(c, f))))[1])
	c.sort()
	i = 0
	while traveled < N:
		traveled += f[i]
		total += f[i] * c[i]
		i += 1
	if traveled > N:
		total -= (traveled - N) * c[i - 1]
	print(total)


for _ in range(int(input())):
	n = int(input())
	fuel = list(map(int, input().split()))
	price = list(map(int, input().split()))
	pair = [[price[i], fuel[i]] for i in range(n)]
	pair.sort(key=lambda x: x[0])
	ans = 0
	temp = 0
	for (i, j) in pair:
		if not n:
			break
		val = min(n, j)
		n -= val
		ans += i * val
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	arr = sorted([(l1[i], l2[i]) for i in range(n)], key=lambda x: x[1])
	cost = 0
	d_c = 0
	for i in range(n):
		if d_c + arr[i][0] >= n:
			fuel_need = n - d_c
			cost += fuel_need * arr[i][1]
			break
		else:
			d_c += arr[i][0]
			cost += arr[i][0] * arr[i][1]
	print(cost)


import os.path
import sys
from math import *
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def inp():
	return sys.stdin.readline().strip()
for _ in range(int(inp())):
	n = int(input())
	arr = list(map(int, inp().split()))
	brr = list(map(int, inp().split()))
	ml = sorted([[brr[i], arr[i]] for i in range(n)])
	(x, res) = [0] * 2
	while n > 0:
		if ml[x][1] > n:
			ml[x][1] = n
		res += ml[x][0] * ml[x][1]
		n -= ml[x][1]
		x += 1
	print(res)


for i in range(int(input())):
	n = int(input())
	fi = list(map(int, input().split()))
	ci = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append([ci[i], fi[i]])
	a.sort()
	c = 0
	fue = 0
	for i in range(n):
		fu = min(a[i][1], n - fue)
		c += fu * a[i][0]
		fue += fu
		if fue == n:
			break
	print(c)


T = int(input())
for i in range(T):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	sorted_indices = [i[0] for i in sorted(enumerate(cost), key=lambda i: i[1])]
	ans = 0
	distleft = n
	for car in sorted_indices:
		cardist = min(fuel[car], distleft)
		distleft -= cardist
		ans += cardist * cost[car]
		if distleft == 0:
			break
	print(ans)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
test = 1
test = int(input())
for _ in range(test):
	(n,) = get_ints()
	a = get_array()
	b = get_array()
	c = []
	for i in range(n):
		c.append([b[i], a[i]])
	c.sort()
	cost = 0
	fuel = 0
	for i in range(n):
		x = min(c[i][1], n - fuel)
		cost += x * c[i][0]
		fuel += x
		if fuel == n:
			break
	print(cost)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [0] * n
	i = 0
	for ele in list(map(int, input().split())):
		arr[i] = [ele, i]
		i += 1
	costs = list(map(int, input().split()))
	prevArrCosts = {}
	for i in range(len(costs)):
		prevArrCosts[i] = costs[i]
	costs.sort()
	arr = sorted(arr, key=lambda k: prevArrCosts[k[1]])
	arr = [l[0] for l in arr]
	fuel = 0
	amount = 0
	for i in range(n):
		fill = min(arr[i], n - fuel)
		amount += fill * costs[i]
		fuel += fill
		if fuel == n:
			print(amount)
			break
	else:
		print('not possible')


for _ in range(int(input())):
	n = int(input())
	z = list(zip(list(map(int, input().split())), list(map(int, input().split()))))
	z.sort(key=lambda x: x[1])
	price = 0
	for i in range(n):
		if z[i][0] >= n:
			price += n * z[i][1]
			break
		else:
			price += z[i][0] * z[i][1]
			n -= z[i][0]
	print(price)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	z = list(zip(c, f))
	z.sort()
	m = n
	price = 0
	for i in range(n):
		if z[i][1] >= m:
			price += m * z[i][0]
			break
		else:
			price += z[i][1] * z[i][0]
			m -= z[i][1]
	print(price)


for u in range(int(input())):
	n = int(input())
	gas = list(map(int, input().split()))[:n]
	cost = list(map(int, input().split()))[:n]
	list1 = []
	for i in range(0, len(gas), 1):
		list1.append([cost[i], gas[i]])
	list1.sort()
	distleft = n
	totalcost = 0
	for j in range(0, len(list1), 1):
		cardist = min(list1[j][1], distleft)
		distleft -= cardist
		totalcost += list1[j][0] * cardist
		if distleft <= 0 or j == len(list1) - 1:
			break
	print(totalcost)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[i] = [c[i], f[i]]
	a = list(d.values())
	a.sort(key=lambda x: x[0])
	litres = 0
	coins = 0
	for car in a:
		if litres >= n:
			break
		l = min(car[1], n - litres)
		price = l * car[0]
		litres += l
		coins += price
	print(coins)


for _ in range(int(input())):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	sort = [item[0] for item in sorted(enumerate(cost), key=lambda item: item[1])]
	distleft = n
	ans = 0
	for car in sort:
		cardist = min(fuel[car], distleft)
		distleft -= cardist
		ans += cardist * cost[car]
		if distleft == 0:
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	cap = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	indices = [i[0] for i in sorted(enumerate(cost), key=lambda i: i[1])]
	distLeft = n
	ans = 0
	for car in indices:
		carDist = min(cap[car], distLeft)
		distLeft -= carDist
		ans += carDist * cost[car]
		if distLeft <= 0:
			break
	print(ans)


t = int(input())
for T in range(t):
	nu = int(input())
	fuel = list(map(int, input().split()))
	coin = list(map(int, input().split()))
	a = []
	for i in range(len(coin)):
		a.append((coin[i], fuel[i]))
	sorta = sorted(a)
	cnt = 0
	ans = 0
	for i in range(len(sorta)):
		if cnt >= nu:
			break
		if sorta[i][1] != 0:
			if cnt + sorta[i][1] > nu:
				b = nu - cnt
				cnt = nu
			else:
				cnt += sorta[i][1]
				b = sorta[i][1]
			ans += b * sorta[i][0]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	indices = [i[0] for i in sorted(enumerate(c), key=lambda x: x[1])]
	distance = n
	min_cost = 0
	for value in indices:
		dist = min(f[value], distance)
		distance = distance - dist
		min_cost += dist * c[value]
		if distance <= 0:
			break
	print(min_cost)


from sys import stdin, stdout
input = stdin.readline
import math, bisect
from itertools import permutations
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([c[i], f[i]])
	l.sort()
	tot = 0
	ans = 0
	for i in range(n):
		if tot + l[i][1] <= n:
			ans += l[i][0] * l[i][1]
			tot += l[i][1]
		else:
			ans += l[i][0] * (n - tot)
			tot = n
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cf = []
	for i in range(n):
		cf.append((c[i], f[i]))
	cf.sort(key=lambda x: x[0])
	cost = 0
	rem = n
	for i in range(n):
		selectedFuel = min(rem, cf[i][1])
		rem -= selectedFuel
		cost += selectedFuel * cf[i][0]
		if rem == 0:
			break
	print(cost)


t = int(input())
for i in range(t):
	n = int(input())
	gasoline = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	arr = []
	for i in range(len(cost)):
		arr.append((cost[i], gasoline[i]))
	arr = sorted(arr)
	(current_cost, current_gasoline) = (0, 0)
	for cars in arr:
		if current_gasoline + cars[1] >= n:
			current_cost += cars[0] * (n - current_gasoline)
			break
		else:
			current_cost += cars[0] * cars[1]
			current_gasoline += cars[1]
	print(current_cost)


def solve(n, F, C):
	F = [f for (_, f) in sorted(zip(C, F))]
	C = sorted(C)
	s = sum(F)
	surplusCapacity = s - n
	i = n - 1
	while i > -1 and surplusCapacity - F[i] >= 0:
		surplusCapacity -= F[i]
		F[i] = 0
		i -= 1
	F[i] -= surplusCapacity
	totalCoins = 0
	for i in range(n):
		totalCoins += F[i] * C[i]
	return totalCoins
t = int(input())
for i in range(t):
	n = int(input())
	F = list(map(int, input().split()))
	C = list(map(int, input().split()))
	result = solve(n, F, C)
	print(result)


for _ in range(int(input())):
	n = int(input())
	fuels = list(map(int, input().split()))
	coins = list(map(int, input().split()))
	temp = []
	for i in range(n):
		temp.append([coins[i], fuels[i]])
	temp.sort()
	cost = fuel = 0
	for i in range(n):
		if fuel >= n:
			break
		else:
			cost += temp[i][1] * temp[i][0]
			fuel += temp[i][1]
	if fuel != n:
		extra = fuel - n
		cost -= extra * temp[i - 1][0]
	print(cost)


t = int(input())
for _ in range(t):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	cl = []
	for i in range(n):
		cl.append((cost[i], fuel[i]))
	sort_cl = sorted(cl)
	dis = 0
	price = 0
	for i in range(n):
		if dis >= n:
			break
		if sort_cl[i][1] != 0:
			if dis + sort_cl[i][1] > n:
				z = n - dis
				dis = n
			else:
				dis += sort_cl[i][1]
				z = sort_cl[i][1]
			price += z * sort_cl[i][0]
	print(price)


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
for _ in range(int(inp())):
	n = int(inp())
	f = lmp()
	c = lmp()
	ml = [(c[i], f[i]) for i in range(n)]
	ml.sort()
	cost = 0
	i = 0
	d = 0
	while d < n:
		j = min(ml[i][1], n - d)
		cost += ml[i][0] * j
		d += j
		i += 1
	print(cost)


for t in range(int(input())):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	total = [[fuel[i], cost[i]] for i in range(n)]
	total.sort(key=lambda x: x[1])
	dist = 0
	cost = 0
	i = 0
	while dist < n and i < n:
		if dist + total[i][0] <= n:
			dist += total[i][0]
			cost += total[i][1] * total[i][0]
		else:
			x = n - dist
			if x <= total[i][0]:
				dist += x
				cost += total[i][1] * x
		i += 1
	print(cost)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	sortedIndices = [item[0] for item in sorted(enumerate(c), key=lambda item: item[1])]
	distLeft = n
	ans = 0
	for car in sortedIndices:
		carDist = min(distLeft, f[car])
		distLeft -= carDist
		ans += carDist * c[car]
		if distLeft == 0:
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	v = []
	for i in range(n):
		v.append([c[i], f[i]])
	v.sort()
	tot = 0
	ans = 0
	i = 0
	while tot < n:
		diff = v[i][1] if v[i][1] + tot <= n else n - tot
		tot += v[i][1]
		ans += diff * v[i][0]
		i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	l = list()
	for i in range(n):
		l.append([f[i], c[i]])
	netFuelRequired = n
	l = sorted(l, key=lambda x: x[1])
	i = 0
	cost = 0
	while netFuelRequired != 0:
		if l[i][0] <= netFuelRequired:
			cost += l[i][0] * l[i][1]
			netFuelRequired -= l[i][0]
		else:
			cost += netFuelRequired * l[i][1]
			netFuelRequired = 0
		i += 1
	print(cost)


test = int(input())
for i in range(0, test):
	n = int(input())
	litres = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	sorted_ind = [item[0] for item in sorted(enumerate(arr), key=lambda item: item[1])]
	i = 0
	z = n
	cost = 0
	i = 0
	while True:
		if z <= 0:
			break
		elif z - litres[sorted_ind[i]] >= 0:
			z = z - litres[sorted_ind[i]]
			cost = cost + litres[sorted_ind[i]] * arr[sorted_ind[i]]
		else:
			cost = cost + arr[sorted_ind[i]] * z
			break
		i = i + 1
	print(cost)


T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	f = list(map(int, input().strip().split(' ')))
	c = list(map(int, input().strip().split(' ')))
	combined = [[i, j] for (i, j) in zip(f, c)]
	combined = sorted(combined, key=lambda x: int(x[1]))
	cost = 0
	gas = N
	for i in range(N):
		req = min(gas, combined[i][0])
		gas -= req
		cost += req * combined[i][1]
		if gas == 0:
			break
	print(cost)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = [int(x) for x in input().split()]
	x = []
	for i in range(n):
		x.append([m[i], l[i]])
	x = sorted(x, key=lambda x: x[0])
	ans = 0
	liter = 0
	for i in range(n):
		ans += x[i][0] * max(0, min(n - liter, x[i][1]))
		liter += min(n - liter, x[i][1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	comb = []
	for i in range(n):
		comb.append([cost[i], fuel[i]])
	comb.sort()
	curcost = 0
	need = n
	for i in range(n):
		cc = comb[i][0]
		cf = comb[i][1]
		if cf >= need:
			curcost += need * cc
			break
		else:
			curcost += cf * cc
			need -= cf
	print(curcost)


def Gasoline(n, FUEL, COST):
	sortedIndex = [item[0] for item in sorted(enumerate(COST), key=lambda item: item[1])]
	DistandeLeft = n
	minimalCost = 0
	for car in sortedIndex:
		carDist = min(FUEL[car], DistandeLeft)
		DistandeLeft -= carDist
		minimalCost += COST[car] * carDist
		if DistandeLeft == 0:
			break
	return minimalCost
T = int(input())
for t in range(T):
	n = int(input())
	FUEL = list(map(int, input().split()))
	COST = list(map(int, input().split()))
	result = Gasoline(n, FUEL, COST)
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append((c[i], f[i]))
	a.sort()
	cost = 0
	distance = 0
	for i in range(n):
		if distance >= n:
			break
		if a[i][1] != 0:
			if distance + a[i][1] > n:
				b = n - distance
				distance = n
			else:
				distance += a[i][1]
				b = a[i][1]
			cost += b * a[i][0]
	print(cost)


def boom1(i):
	return zipped[i][0] * zipped[i][1]

def boom():
	(sss, answer) = (0, 0)
	for i in range(nn):
		if sss + zipped[i][1] >= nn:
			answer += (nn - sss) * zipped[i][0]
		else:
			answer += boom1(i)
		sss += zipped[i][1]
		if sss >= nn:
			break
	return answer
for q in range(int(input())):
	nn = int(input())
	(oop1, oop2) = (list(map(int, input().split())), list(map(int, input().split())))
	zipped = sorted(zip(oop2, oop1))
	print(boom())


tc = int(input())
for t in range(tc):
	n = int(input())
	max_gas = [int(i) for i in input().split()]
	cost = [int(i) for i in input().split()]
	lst = [(cost[i], max_gas[i]) for i in range(len(cost))]
	srtd = sorted(lst)
	tank = 0
	ans = 0
	for i in range(len(srtd)):
		if tank >= n:
			break
		if srtd[i][1] + tank > n:
			ltrs = n - tank
			tank = n
			ans += srtd[i][0] * ltrs
		else:
			ltrs = srtd[i][1]
			tank += ltrs
			ans += srtd[i][0] * ltrs
	print(ans)


def coins(total, cars, val):
	arr = list(zip(cars, val))
	arr.sort(key=lambda x: x[1])
	i = 0
	distance = 0
	coins = 0
	while distance != total:
		if total - distance < arr[i][0]:
			coins = coins + (total - distance) * arr[i][1]
			distance = total
		else:
			distance = distance + arr[i][0]
			coins = coins + arr[i][0] * arr[i][1]
			i = i + 1
	return coins
num = int(input())
for i in range(num):
	total = int(input())
	cars = list(map(int, input().split()))
	val = list(map(int, input().split()))
	print(coins(total, cars, val))


t = int(input())
for _ in range(t):
	n = int(input())
	rem = n
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	g = [[c[i], f[i]] for i in range(n)]
	g.sort()
	ans = 0
	i = 0
	while i < n:
		fuel = g[i][1]
		cst = g[i][0]
		if fuel < rem:
			rem -= fuel
			ans += cst * fuel
		else:
			ans += cst * rem
			rem = 0
		if rem == 0:
			break
		i += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	fuel = list(map(int, input().split(' ')))
	cost = list(map(int, input().split(' ')))
	sortedCost = [item[0] for item in sorted(enumerate(cost), key=lambda item: item[1])]
	distance = n
	answer = 0
	for car in sortedCost:
		carDistance = min(fuel[car], distance)
		distance -= carDistance
		answer += carDistance * cost[car]
		if distance == 0:
			break
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	capacity = list(map(int, input().strip().split()))
	price = list(map(int, input().strip().split()))
	relation = dict()
	for i in range(n):
		p = price[i]
		c = capacity[i]
		if p not in relation:
			relation[p] = c
		else:
			relation[p] += c
	sorted_price = sorted(relation)
	net_capacity = 0
	net_price = 0
	for p in sorted_price:
		c = relation[p]
		if net_capacity + c < n:
			net_price += c * p
			net_capacity += c
		else:
			net_price += (n - net_capacity) * p
			break
	print(net_price)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	e = list(map(int, input().split()))
	l = list()
	for i in range(n):
		l.append((e[i], f[i]))
	l.sort()
	ans = 0
	su = 0
	for i in range(n):
		if l[i][1] + su <= n:
			su += l[i][1]
			ans += l[i][0] * l[i][1]
		else:
			ans += (n - su) * l[i][0]
			break
	print(ans)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	s = []
	for (a, b) in zip(c, f):
		s.append([a, b])
	s.sort()
	cur = 0
	ans = 0
	for j in s:
		if cur + j[1] <= n:
			cur += j[1]
			ans += j[0] * j[1]
		else:
			ans += j[0] * (n - cur)
			break
	print(ans)


T = int(input())
for i in range(0, T):
	N = int(input())
	f = list(map(int, input().split(' ')))
	c = list(map(int, input().split(' ')))
	cost = 0
	coin_fuel = sorted(zip(c, f))
	i = 0
	while True:
		cost = cost + min(coin_fuel[i][1], N) * coin_fuel[i][0]
		N = N - min(coin_fuel[i][1], N)
		if N == 0:
			print(cost)
			break
		i = i + 1


for _ in range(int(input())):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	sorted_indicesC = [i[0] for i in sorted(enumerate(cost), key=lambda x: x[1])]
	ans = 0
	distleft = n
	for i in sorted_indicesC:
		temp = min(fuel[i], distleft)
		distleft -= temp
		ans += temp * cost[i]
		if distleft == 0:
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	capacity = list(map(int, input().split()))
	coins = list(map(int, input().split()))
	if coins == [coins[0]] * n:
		print(n * coins[0])
	elif capacity.count(0) == n - 1:
		i = capacity.index(max(capacity))
		c = coins[i]
		print(c * n)
	else:
		i = coins.index(min(coins))
		if capacity[i] >= n:
			c = coins[i]
			print(c * n)
		else:
			a = []
			for i in range(n):
				a.append([coins[i], capacity[i]])
			a = sorted(a)
			cost = 0
			rem = n
			for el in a:
				if rem == 0:
					break
				elif el[1] > rem:
					cost += rem * el[0]
					rem = 0
				else:
					cost += el[1] * el[0]
					rem -= el[1]
			print(cost)


for lol in range(int(input())):
	n = int(input())
	(f, c) = (list(map(int, input().split())), list(map(int, input().split())))
	(a, b, bc) = (sorted(c), [], [])
	for i in range(n):
		t = []
		t.append(c[i])
		t.append(f[i])
		b.append(t)
	b.sort()
	(tgt, cost) = (n, 0)
	for i in range(len(b)):
		amt = min(tgt, b[i][1])
		cost += amt * b[i][0]
		tgt -= amt
		if tgt <= 0:
			break
	print(cost)


import numpy as np
x = int(input())
for _ in range(x):
	n = int(input())
	l = list(map(int, input().split()))
	c = list(map(int, input().split()))
	k = np.argsort(c)
	(d, cost, i) = (0, 0, 0)
	while d < n:
		d += l[k[i]]
		cost += c[k[i]] * l[k[i]]
		i += 1
	if d > n:
		cost = cost - (d - n) * c[k[i - 1]]
	print(cost)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr1 = list(map(int, input().split(' ')))
	sort = [item[0] for item in sorted(enumerate(arr1), key=lambda item: item[1])]
	dis = n
	dis1 = 0
	ans = 0
	for i in sort:
		dis1 = min(dis, arr[i])
		dis -= dis1
		ans += dis1 * arr1[i]
		if dis == 0:
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	d = []
	car = list(map(int, input().split(' ')))
	cost = list(map(int, input().split(' ')))
	for j in range(0, len(car)):
		d.append((cost[j], car[j]))
	d.sort()
	total = 0
	for k in range(len(car)):
		if n <= 0:
			break
		if d[k][1] != 0:
			if d[k][1] < n:
				total = total + d[k][0] * d[k][1]
				n = n - d[k][1]
			else:
				total = total + n * d[k][0]
				n = 0
	print(total)


t = int(input())
for test in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cost = 0
	km = n
	l = sorted(zip(c, f))
	(c, f) = zip(*l)
	for i in range(n):
		if km >= f[i]:
			km -= f[i]
			cost += c[i] * f[i]
		else:
			cost += c[i] * km
			km = 0
		if km == 0:
			break
	print(cost)


t = int(input())
for _ in range(t):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	li = []
	for i in range(n):
		li.append([cost[i], i])
	li.sort()
	sort_index = []
	for x in li:
		sort_index.append(x[1])
	distance = n
	ans = 0
	for j in sort_index:
		carDist = min(fuel[j], distance)
		distance -= carDist
		ans += cost[j] * carDist
		if distance == 0:
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	merged = []
	for i in range(n):
		merged.append((c[i], f[i]))
	merged = sorted(merged)
	req_fuel = n
	total_cost = 0
	for i in range(n):
		no = merged[i][1]
		if no > req_fuel:
			no = req_fuel
		total_cost += no * merged[i][0]
		req_fuel -= no
		if req_fuel == 0:
			break
	print(total_cost)


for _ in range(int(input())):
	N = int(input())
	fuel = [int(x) for x in input().split()]
	cost = [int(x) for x in input().split()]
	sortedIndices = [item[0] for item in sorted(enumerate(cost), key=lambda item: item[1])]
	final_cost = 0
	distance_left = N
	distance_travelled = 0
	for car in sortedIndices:
		distance_travelled = min(fuel[car], distance_left)
		distance_left = distance_left - distance_travelled
		final_cost += distance_travelled * cost[car]
		if distance_left == 0:
			break
	print(final_cost)


for _ in range(int(input())):
	n = int(input())
	f = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	de = [(c[i], f[i]) for i in range(n)]
	de.sort()
	k = 0
	i = 0
	ans = 0
	while k < n:
		lm = n - k
		ans += min(lm, de[i][1]) * de[i][0]
		k += min(lm, de[i][1])
		i += 1
	print(ans)


t = int(input())

def sortSecond(val):
	return val[1]
for i in range(t):
	n = int(input())
	(answer, temp) = (0, n)
	fuel = list(map(int, input().split()))
	coins = list(map(int, input().split()))
	zipped = list(zip(fuel, coins))
	zipped.sort(key=sortSecond)
	for i in range(n):
		if temp > 0:
			if temp - zipped[i][0] <= 0:
				answer += temp * zipped[i][1]
				temp = 0
			else:
				answer += zipped[i][0] * zipped[i][1]
				temp -= zipped[i][0]
		else:
			break
	print(answer)


import numpy
for i in range(int(input())):
	N = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	c = cost
	s = numpy.array(c)
	sort_index = numpy.argsort(s)
	left = N
	ans = 0
	for car in sort_index:
		car_dist = min(fuel[car], left)
		left = left - car_dist
		ans += car_dist * cost[car]
		if left == 0:
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	cf = []
	f = list(map(int, input().split(' ')))
	c = list(map(int, input().split(' ')))
	for i in range(n):
		cf.append([c[i], f[i]])
	cf.sort()
	flag = 1
	total = 0
	fuel = 0
	distance = 0
	for i in range(n):
		if fuel >= n:
			print(total)
			flag = 0
			break
		else:
			temp = min(cf[i][1], n - distance)
			distance = distance + temp
			fuel = fuel + temp
			total = total + cf[i][0] * temp
	if flag:
		print(total)


t = int(input())
for _ in range(t):
	n = int(input())
	f = list(map(int, input().split(' ')))
	c = list(map(int, input().split(' ')))
	cost = 0
	dist = n
	comb = list(zip(c, f))
	comb.sort()
	c = comb[0]
	f = comb[1]
	ch_c = []
	ch_f = []
	for (i, j) in comb:
		ch_c.append(i)
		ch_f.append(j)
	for i in range(n):
		fuel = min(dist, ch_f[i])
		cost += fuel * ch_c[i]
		dist -= fuel
		if dist == 0:
			break
	print(cost)


try:
	for i in range(int(input())):
		n = int(int(input()))
		f = [int(i) for i in input().split()]
		c = [int(i) for i in input().split()]
		ans = list(zip(f, c))
		ans.sort(key=lambda x: x[1])
		x = 0
		for i in ans:
			er = min(i[0], n)
			n -= er
			x += er * i[1]
		print(x)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	fi = list(map(int, input().split()))
	ci = list(map(int, input().split()))
	fc = list(zip(fi, ci))
	fc.sort(key=lambda e: e[1])
	ans = 0
	for (f, c) in fc:
		cnt = min(f, n)
		n -= cnt
		ans += cnt * c
	print(ans)


from bisect import insort
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	a = [(f[i], c[i], i) for i in range(n)]
	a.sort(key=lambda x: x[1])
	p = 0
	t = 0
	for i in range(n):
		if p + a[i][0] >= n:
			t += (n - p) * a[i][1]
			break
		t += a[i][0] * a[i][1]
		p += a[i][0]
	print(t)


t = int(input())
for _ in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([f[i], c[i]])
	l = sorted(l, key=lambda x: x[1])
	t = n
	c = 0
	for i in range(n):
		if l[i][0] < t:
			t -= l[i][0]
			c += l[i][0] * l[i][1]
		else:
			c += t * l[i][1]
			break
	print(c)


t = int(input())
for i in range(0, t):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	li = [i[0] for i in sorted(enumerate(c), key=lambda x: x[1])]
	re = n
	co = 0
	for j in range(0, n):
		y = min(f[li[j]], re)
		re = re - y
		co += c[li[j]] * y
		if re == 0:
			break
	print(co)


for _ in range(int(input())):
	n = int(input())
	fi = list(map(int, input().split()))
	ci = list(map(int, input().split()))
	Si = list(enumerate(ci))
	new = [x[0] for x in sorted(Si, key=lambda x: x[1])]
	d = n
	cost = 0
	for i in new:
		cd = min(fi[i], d)
		cost += cd * ci[i]
		d -= cd
		if d == 0:
			break
	print(cost)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	coin = list(map(int, input().split()))
	coins = 0
	dist = n
	clist = [i[0] for i in sorted(enumerate(coin), key=lambda x: x[1])]
	for j in clist:
		car = min(f[j], dist)
		dist -= car
		coins += car * coin[j]
		if dist == 0:
			break
	print(coins)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	new = enumerate(c)
	a = dict(new)
	a = dict(sorted(a.items(), key=lambda item: item[1]))
	b = []
	for key in a:
		b.append(key)
	left_dist = n
	i = 0
	cost = 0
	while left_dist > 0:
		if left_dist > f[b[i]]:
			left_dist = left_dist - f[b[i]]
			cost = f[b[i]] * c[b[i]] + cost
		else:
			cost = left_dist * c[b[i]] + cost
			left_dist = 0
		i = i + 1
	print(cost)


for _ in range(int(input())):
	N = int(input())
	FUEL = list(map(int, input().split()))
	COST = list(map(int, input().split()))
	sortedindC = [i[0] for i in sorted(enumerate(COST), key=lambda i: i[1])]
	dist = N
	ans = 0
	for i in sortedindC:
		car = min(FUEL[i], dist)
		dist -= car
		ans += car * COST[i]
		if dist == 0:
			break
	print(ans)


def solve(n, a, b):
	combo = list()
	for i in range(n):
		combo.append((b[i], a[i]))
	qwerty = sorted(combo)
	cnt = 0
	res = 0
	for i in range(n):
		if cnt >= n:
			break
		if qwerty[i][1] != 0:
			if cnt + qwerty[i][1] > n:
				mht = n - cnt
				cnt = n
			else:
				cnt += qwerty[i][1]
				mht = qwerty[i][1]
			res += mht * qwerty[i][0]
	return res
noOfTestCases = int(input())
for i in range(noOfTestCases):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = solve(n, a, b)
	print(ans)


import sys
import math
import bisect
from math import sqrt

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

def iinput():
	return int(input())

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

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = int(1000000000.0) + 7
for _ in range(iinput()):
	n = iinput()
	f = get_list()
	c = get_list()
	c2 = list(enumerate(c))
	c2.sort(key=lambda x: x[1])
	f2 = [f[item[0]] for item in c2]
	cost = 0
	distLeft = n
	for i in range(n):
		distComp = min(distLeft, f2[i])
		cost += distComp * c2[i][1]
		distLeft -= distComp
		if distLeft <= 0:
			break
	print(cost)


import sys, io, os, time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'
input = sys.stdin.readline
for ii in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	arr = [[c[i], f[i], i] for i in range(n)]
	arr.sort(key=lambda x: (x[0], x[1]))
	ans = 0
	rem = n
	for i in range(n):
		if rem:
			need = min(arr[i][1], rem)
			ans += arr[i][0] * need
			rem -= need
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	coin = list(map(int, input().split()))
	c = 0
	a = []
	for i in range(len(f)):
		a.append((coin[i], f[i]))
	a1 = sorted(a)
	ans = n
	i = 0
	while ans > 0:
		if a1[i][1] >= ans:
			c += a1[i][0] * ans
			break
		else:
			t = a1[i][0] * a1[i][1]
			ans = ans - a1[i][1]
			c += t
		i += 1
	print(c)


import math

def solve():
	n = int(input())
	fuel = list(map(int, input().split()))
	coin = list(map(int, input().split()))
	a = []
	for i in range(len(coin)):
		a.append((coin[i], fuel[i]))
	a.sort()
	cnt = 0
	ans = 0
	for i in range(len(a)):
		if cnt >= n:
			break
		if a[i][1] != 0:
			if cnt + a[i][1] > n:
				b = n - cnt
				cnt = n
			else:
				cnt += a[i][1]
				b = a[i][1]
			ans += b * a[i][0]
	print(ans)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	g = [i[0] for i in sorted(enumerate(c), key=lambda i: i[1])]
	ans = 0
	rem = n
	for j in g:
		d = min(f[j], rem)
		rem = rem - d
		ans += c[j] * d
		if rem == 0:
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	fuel = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	price = list(zip(cost, fuel))
	price.sort()
	amount = 0
	for (c, f) in price:
		t = min(n, f)
		amount += c * t
		n -= t
		if n <= 0:
			break
	print(amount)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	c = list(map(int, input().split()))
	z = [(c[i], f[i]) for i in range(n)]
	z.sort(key=lambda x: x[0])
	dis = 0
	cos = 0
	for item in z:
		if dis >= n:
			break
		k = min(n - dis, item[1])
		dis += k
		cos += k * item[0]
	print(cos)


for _ in range(int(input())):
	n = int(input())
	fi = [int(i) for i in input().split()]
	ci = [int(j) for j in input().split()]
	fici = []
	for i in range(n):
		fici.append({'fi': fi[i], 'ci': ci[i]})
	s_fici = sorted(fici, key=lambda k: k['ci'])
	number_of_litres = 0
	cost = 0
	for i in s_fici:
		if n - number_of_litres > 0:
			fuel_taken = i['fi'] if i['fi'] <= n - number_of_litres else n - number_of_litres
			cost += fuel_taken * i['ci']
			number_of_litres += fuel_taken
	print(cost)


def Ans(L, n):
	L.sort(key=lambda x: x[1])
	cost = 0
	req = n
	for i in L:
		take = min(req, i[0])
		cost += take * i[1]
		req -= take
	if req == 0:
		return cost
t = int(input())
for _ in range(t):
	n = int(input())
	F = list(map(int, input().split()))
	C = list(map(int, input().split()))
	L = []
	for i in range(n):
		L.append([F[i], C[i]])
	print(Ans(L, n))


try:
	from collections import deque
	t = int(input())
	for _ in range(t):
		n = int(input())
		cost = 0
		f = list(map(int, input().split()))
		c = list(map(int, input().split()))
		l = [x[0] for x in sorted(enumerate(c), key=lambda item: item[1])]
		l = deque(l)
		distleft = n
		while True:
			index = l.popleft()
			cardist = min(f[index], distleft)
			cost += c[index] * cardist
			distleft -= cardist
			if distleft == 0:
				print(cost)
				break
except EOFError:
	pass


T = int(input())
for _ in range(T):
	N = int(input())
	F = [int(n) for n in input().split()]
	C = [int(n) for n in input().split()]
	F_C = []
	for i in range(N):
		F_C.append([F[i], C[i], i])
	F_C = [item[2] for item in sorted(F_C, key=lambda e: e[1])]
	dist = N
	min_cost = 0
	ind = 0
	while dist > 0:
		min_cost += min(dist, F[F_C[ind]]) * C[F_C[ind]]
		dist -= F[F_C[ind]]
		ind += 1
	print(min_cost)


def factComb(cost, cap, n):
	if n <= 1:
		return 0
	comb = [(cost[i], cap[i]) for i in range(n)]
	comb.sort()
	tot_cost = 0
	fuel_left = n
	for i in range(n):
		consume = min(comb[i][1], fuel_left)
		tot_cost += consume * comb[i][0]
		fuel_left -= consume
		if fuel_left == 0:
			break
	return tot_cost
t = int(input())
for i in range(t):
	n = int(input())
	f = [int(x) for x in input().split()]
	cost = [int(x) for x in input().split()]
	print(factComb(cost, f, n))