Alice gives Bob a board composed of $1\times1$ wooden squares and asks him to find the minimum cost of breaking the board back down into its individual squares. To break the board down, Bob must make cuts along its horizontal and vertical lines. 

To reduce the board to squares, Bob makes horizontal and vertical cuts across the entire board.  Each cut has a given cost, $cost\text{_}y[i]$ or $cost\text{_}x[j]$ for each cut along a row or column across one board, so the cost of a cut must be multiplied by the number of segments it crosses.  The cost of cutting the whole board down into $1\times1$ squares is the sum of the costs of each successive cut.   

Can you help Bob find the minimum cost?  The number may be large, so print the value modulo $10^9+7$.

For example, you start with a $2\times2$ board.  There are two cuts to be made at a cost of $cost\text{_}y[1]=3$ for the horizontal and $cost\text{_}x[1]=1$ for the vertical.  Your first cut is across $1$ piece, the whole board.  You choose to make the horizontal cut between rows $1$ and $2$ for a cost of $1\times3=3$.  The second cuts are vertical through the two smaller boards created in step $\mbox{I}$ between columns $1$ and $2$.  Their cost is $2\times1=2$.  The total cost is $3+2=5$ and $5\%(10^9+7)=5$.

Function Description  

Complete the boardCutting function in the editor below.  It should return an integer.  

boardCutting has the following parameter(s):  

cost_x: an array of integers, the costs of vertical cuts  
cost_y: an array of integers, the costs of horizontal cuts  

Input Format

The first line contains an integer $\textit{q}$, the number of queries.

The following $\textit{q}$ sets of lines are as follows:

The first line has two positive space-separated integers $m$ and $n$, the number of rows and columns in the board.    
The second line contains $m-1$ space-separated integers cost_y[i], the cost of a  horizontal cut between rows $\left[i\right]$ and $\left[i+1\right]$ of one board.
The third line contains $n-1$ space-separated integers cost_x[j], the cost of a vertical cut between columns $\left[j\right]$ and $[j+1]$ of one board.

Constraints

$1\leq q\leq20$  
$2\leq m,n\leq1000000$       
$0\leq c o s t\text{_}y[i],cost\text{_}x[j]\leq10^9$   

Output Format

For each of the $\textit{q}$ queries, find the minimum cost ($minCost$) of cutting the board into $1\times1$ squares and print the value of $minCost\%(10^9+7)$.

Sample Input 0

1
2 2
2
1

Sample Output 0

4

Explanation 0 

We have a $2\times2$ board, with cut costs $cost\text{_}y[1]=2$ and $cost\text{_}x[1]=1$. Our first cut is horizontal between $y[1]$ and $y[2]$, because that is the line with the highest cost ($2$). Our second cut is vertical, at $x[1]$. Our first cut has a $totalCost$ of $2$ because we are making a cut with cost $cost\text{_}y[1]=2$ across $1$ segment, the uncut board. The second cut also has a $totalCost$ of $2$ but we are making a cut of cost $cost\text{_}x[1]=1$ across $2$ segments. Our answer is $minCost=((2\times1)+(1\times2))\ \text{\%}\ (10^9+7)=4$.

Sample Input 1

1
6 4
2 1 3 1 4
4 1 2

Sample Output 1  

42

Explanation 1 

Our sequence of cuts is: $y[5]$, $x[1]$, $y[3]$, $y[1]$, $x[3]$, $y[2]$, $\boldsymbol{y}\left[4\right]$ and $x[2]$. 

Cut 1: Horizontal with cost $\text{cost}_{-}y[5]=4$ across $1$ segment. $totalCost=4\times1=4$. 

Cut 2: Vertical with cost $cost\text{_}x[1]=4$ across $2$ segments. $totalCost=4\times2=8$. 

Cut 3: Horizontal with cost $cost\text{_}y[3]=3$ across $2$ segments. $totalCost=3\times2=6$. 

Cut 4: Horizontal with cost $cost\text{_}y[1]=2$ across $2$ segments. $totalCost=2\times2=4$. 

Cut 5: Vertical with cost $cost\text{_}x[3]=2$ across $4$ segments. $totalCost=2\times4=8$. 

Cut 6: Horizontal with cost $cost\text{_}y[2]=1$ across $3$ segments. $totalCost=1\times3=3$. 

Cut 7: Horizontal with cost $cost\text{_}y[4]=1$ across $3$ segments. $totalCost=1\times3=3$. 

Cut 8: Vertical with cost $cost\text{_}x[2]=1$ across $\boldsymbol{6}$ segments. $totalCost=1\times6=6$.      

$totalCost=4+8+6+4+8+3+3+6=42$. We then print the value of $42\%(10^9+7)$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for t in range(int(input())):
	(m, n) = map(int, input().split())
	hor = sorted(map(int, input().split()), reverse=True)
	ver = sorted(map(int, input().split()), reverse=True)
	h = v = 0
	ret = 0
	modulo = 10 ** 9 + 7
	for i in range(m + n):
		if h >= len(hor) or v >= len(ver):
			break
		if ver[v] > hor[h]:
			ret += (h + 1) * ver[v] % modulo
			v += 1
		else:
			ret += hor[h] * (v + 1) % modulo
			h += 1
	if h < len(hor):
		ret += sum(hor[h:]) * (v + 1) % modulo
	elif v < len(ver):
		ret += sum(ver[v:]) * (h + 1) % modulo
	print(ret % modulo)


R = 10 ** 9 + 7

def solve():
	(n, m) = map(int, input().split())
	y = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y.sort(reverse=1)
	x.sort(reverse=1)
	lx = len(x)
	ly = len(y)
	ix = 0
	iy = 0
	result = 0
	while ix < lx and iy < ly:
		if x[ix] > y[iy]:
			result += x[ix] * (iy + 1)
			result = result % R
			ix += 1
		elif x[ix] < y[iy]:
			result += y[iy] * (ix + 1)
			result = result % R
			iy += 1
		elif ix > iy:
			result += x[ix] * (iy + 1)
			result = result % R
			ix += 1
		else:
			result += y[iy] * (ix + 1)
			result = result % R
			iy += 1
	if ix < lx:
		sum = 0
		for i in range(ix, lx):
			sum += x[i]
		result += (iy + 1) * sum
		result = result % R
	if iy < ly:
		sum = 0
		for i in range(iy, ly):
			sum += y[i]
		result += (ix + 1) * sum
		result = result % R
	result = result % R
	print(result)
t = int(input())
for i in range(0, t):
	solve()


t = int(input())
while t > 0:
	s = input().split(' ')
	m = s[0]
	n = s[1]
	l1 = map(int, input().split(' '))
	l2 = map(int, input().split(' '))
	y = []
	for i in l1:
		y.append([i, 0])
	for i in l2:
		y.append([i, 1])
	y.sort(reverse=True)
	c = [1, 1]
	su = 0
	for i in y:
		su = (su + i[0] * c[i[1]]) % 1000000007
		c[1 - i[1]] += 1
	print(su)
	t -= 1


t = int(input())
while not t == 0:
	(v, h) = (1, 1)
	a = [int(i) for i in input().split(' ')]
	b = [(int(i), 'h') for i in input().split(' ')]
	c = [(int(i), 'v') for i in input().split(' ')]
	costArr = b + c
	costArr.sort(reverse=True)
	cost = 0
	for tup in costArr:
		if tup[1] == 'h':
			v += 1
			cost += tup[0] * h
		else:
			h += 1
			cost += tup[0] * v
		if cost > 1000000007:
			cost %= 1000000007
	print(cost)
	t -= 1


MOD = 10 ** 9 + 7

def solve_greedy(x, y):
	x.sort()
	y.sort()
	cost = 0
	x_count = y_count = 1
	while x or y:
		if not x or (y and y[-1] > x[-1]):
			cost += y.pop() * x_count
			cost = cost % MOD
			y_count += 1
		else:
			cost += x.pop() * y_count
			cost = cost % MOD
			x_count += 1
	return cost % MOD

def main():
	T = int(input())
	for _ in range(T):
		input()
		x = [int(x) for x in input().split()]
		y = [int(x) for x in input().split()]
		print(solve_greedy(x, y))
main()


tests = int(input())
for t in range(tests):
	(x, y) = [int(val) for val in input().split()]
	xCuts = [int(val) for val in input().split()]
	yCuts = [int(val) for val in input().split()]
	xd = {}
	for e in xCuts:
		if e in xd:
			xd[e] += 1
		else:
			xd[e] = 1
	for e in yCuts:
		if e not in xd:
			xd[e] = 0
	xSplits = 1
	ySplits = 1
	output = 0
	allCuts = sorted(xCuts + yCuts)
	for i in range(len(allCuts) - 1, -1, -1):
		e = allCuts[i]
		if xd[e] > 0:
			xd[e] -= 1
			output += e * xSplits
			ySplits += 1
		else:
			output += e * ySplits
			xSplits += 1
	print(output % 1000000007)


import heapq

def sideindex(sections, slices):
	if len(slices[0]) == 0:
		return 1
	if len(slices[1]) == 0:
		return 0
	if -slices[0][0] > -slices[1][0]:
		return 0
	if -slices[1][0] > -slices[0][0]:
		return 1
	return 0
T = int(input())
for i in range(T):
	(M, N) = [int(v) for v in input().split()]
	y = [-int(v) for v in input().split()]
	x = [-int(v) for v in input().split()]
	heapq.heapify(x)
	heapq.heapify(y)
	cost = 0
	slices = [x, y]
	sections = [1, 1]
	for i in range(M + N - 2):
		side = sideindex(sections, slices)
		otherside = 1 - side
		sliceprice = -heapq.heappop(slices[side])
		cost += sections[side] * sliceprice % 1000000007
		sections[otherside] += 1
	print(cost % 1000000007)


import sys

def f(list_Y, list_X, Y_Seg, X_Seg):
	total = 0
	while True:
		if len(list_Y) and len(list_X):
			if list_Y[0] >= list_X[0]:
				total += list_Y[0] * X_Seg
				Y_Seg += 1
				del list_Y[0]
			else:
				total += list_X[0] * Y_Seg
				X_Seg += 1
				del list_X[0]
		elif len(list_Y) == 0:
			total += sum(list_X) * Y_Seg
			break
		else:
			total += sum(list_Y) * X_Seg
			break
	return total
T = int(sys.stdin.readline().rstrip('\n'))
for i in range(T):
	sys.stdin.readline()
	LY = sorted([int(i) for i in sys.stdin.readline().rstrip('\n').split(' ')], reverse=True)
	LX = sorted([int(i) for i in sys.stdin.readline().rstrip('\n').split(' ')], reverse=True)
	print(f(LY, LX, 1, 1) % (10 ** 9 + 7))


total = []
case = input()
for i in range(int(case)):
	mn = input()
	mn = mn.split()
	m = int(mn[0])
	n = int(mn[1])
	ycost = input()
	xcost = input()
	ycost = ycost.split()
	xcost = xcost.split()
	ycost = [int(i) for i in ycost]
	xcost = [int(i) for i in xcost]
	ycost.sort()
	xcost.sort()
	ycounter = 1
	xcounter = 1
	yindex = len(ycost) - 1
	xindex = len(xcost) - 1
	verCost = 0
	horCost = 0
	while yindex >= 0 and xindex >= 0:
		ymax = ycost[yindex]
		xmax = xcost[xindex]
		if ymax >= xmax:
			horCost += ymax * xcounter
			ycounter += 1
			yindex -= 1
		else:
			verCost += xmax * ycounter
			xcounter += 1
			xindex -= 1
	if yindex >= 0:
		while yindex >= 0:
			horCost += ycost[yindex] * xcounter
			yindex -= 1
	elif xindex >= 0:
		while xindex >= 0:
			verCost += xcost[xindex] * ycounter
			xindex -= 1
	total.append((horCost + verCost) % (10 ** 9 + 7))
for n in total:
	print(n)


import sys, string, math

def read_int_array():
	tmp = input().split(' ')
	l = [0] * len(tmp)
	for i in range(len(tmp)):
		l[i] += int(tmp[i])
	return l
t = int(input())
for i in range(t):
	l = input().split(' ')
	[m, n] = [int(l[0]), int(l[1])]
	x = read_int_array()
	x.sort()
	x.reverse()
	y = read_int_array()
	y.sort()
	y.reverse()
	x_iter = 0
	y_iter = 0
	min = 0
	while x_iter < len(x) or y_iter < len(y):
		if x_iter == len(x):
			min += y[y_iter] * (x_iter + 1)
			y_iter += 1
		elif y_iter == len(y):
			min += x[x_iter] * (y_iter + 1)
			x_iter += 1
		elif x[x_iter] > y[y_iter]:
			min += x[x_iter] * (y_iter + 1)
			x_iter += 1
		elif x[x_iter] == y[y_iter]:
			if x_iter >= y_iter:
				min += x[x_iter] * (y_iter + 1)
				x_iter += 1
			else:
				min += y[y_iter] * (x_iter + 1)
				y_iter += 1
		else:
			min += y[y_iter] * (x_iter + 1)
			y_iter += 1
	print(min % (10 ** 9 + 7))


T = int(input())
for i in range(T):
	(M, N) = input().strip().split()
	M = int(M)
	N = int(N)
	y = input().strip().split()
	x = input().strip().split()
	y = [int(yi) for yi in y]
	x = [int(xi) for xi in x]
	y.sort()
	y.reverse()
	x.sort()
	x.reverse()
	yl = len(y)
	xl = len(x)
	kl = xl + yl
	lst = []
	xy_cost = []
	yi = 0
	xi = 0
	while kl:
		kl -= 1
		if xi >= xl:
			lst += y[yi:]
			xy_cost += [1] * (yl - yi)
			break
		elif yi >= yl:
			lst += x[xi:]
			xy_cost += [0] * (xl - xi)
			break
		elif x[xi] > y[yi]:
			lst.append(x[xi])
			xy_cost.append(0)
			xi += 1
		else:
			lst.append(y[yi])
			xy_cost.append(1)
			yi += 1
	total = 0
	xy_count = [1, 1]
	j = 0
	for e in lst:
		axis = xy_cost[j]
		total += lst[j] * xy_count[axis]
		total %= 1000000007
		xy_count[axis ^ 1] += 1
		j += 1
	print(total)


T = int(input())
nr = 1000000007
for testcase in range(0, T):
	line = input()
	mn = line.split()
	M = int(mn[0])
	N = int(mn[1])
	line = input()
	y = [int(n) for n in line.split()]
	line = input()
	x = [int(n) for n in line.split()]
	hcuts = 0
	vcuts = 0
	x.sort(reverse=True)
	y.sort(reverse=True)
	total = 0
	while True:
		if hcuts < M - 1 and vcuts < N - 1:
			if x[vcuts] >= y[hcuts]:
				total = (total + x[vcuts] * (1 + hcuts)) % nr
				vcuts += 1
			else:
				total = (total + y[hcuts] * (1 + vcuts)) % nr
				hcuts += 1
		elif hcuts < M - 1:
			total = (total + y[hcuts] * (1 + vcuts)) % nr
			hcuts += 1
		elif vcuts < N - 1:
			total = (total + x[vcuts] * (1 + hcuts)) % nr
			vcuts += 1
		else:
			break
	print(total)


for i in range(int(input())):
	(M, N) = map(int, input().split())
	X = map(int, input().split())
	Y = map(int, input().split())
	V = H = 1
	Sum = 0
	for (i, isV) in sorted([(x, True) for x in X] + [(y, False) for y in Y], reverse=True):
		Sum += i * (H if isV else V)
		V += isV
		H += not isV
	print(Sum % (10 ** 9 + 7))


m = 10 ** 9 + 7

def f(X, Y):
	X.sort(reverse=True)
	Y.sort(reverse=True)
	(ix, iy) = (0, 0)
	c = 0
	while ix < len(X) and iy < len(Y):
		if X[ix] > Y[iy]:
			c += (iy + 1) * X[ix]
			c %= m
			ix += 1
		else:
			c += (ix + 1) * Y[iy]
			c %= m
			iy += 1
	while ix < len(X):
		c += (len(Y) + 1) * X[ix]
		c %= m
		ix += 1
	while iy < len(Y):
		c += (len(X) + 1) * Y[iy]
		c %= m
		iy += 1
	return c
for _ in range(int(input())):
	input()
	print(f([int(i) for i in input().split()], [int(i) for i in input().split()]))


for i in range(int(input())):
	(N, M) = map(int, input().split())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	x.sort()
	x.reverse()
	y.sort()
	y.reverse()
	(i, j, cx, cy) = (0, 0, 1, 1)
	ans = 0
	while i < N - 1 and j < M - 1:
		if x[i] >= y[j]:
			ans += x[i] * cy
			cx += 1
			i += 1
		else:
			ans += y[j] * cx
			cy += 1
			j += 1
	i -= 1
	j -= 1
	if i != N - 2:
		for k in range(i + 1, N - 1):
			ans += x[k] * cy
	if j != M - 2:
		for k in range(j + 1, M - 1):
			ans += y[k] * cx
	print(ans % 1000000007)


def quick_sort(l):
	n = len(l)
	if n == 0 or n == 1:
		return l
	p = l[0]
	res1 = []
	res2 = []
	for x in l[1:]:
		if x > p:
			res2.append(x)
		else:
			res1.append(x)
	res1 = quick_sort(res1)
	res2 = quick_sort(res2)
	res = res1 + [p] + res2
	return res
constmod = 10 ** 9 + 7
t = int(input())
for q in range(t):
	(m, n) = [int(i) for i in input().strip().split()]
	m -= 1
	n -= 1
	y = [int(i) for i in input().strip().split()]
	x = [int(i) for i in input().strip().split()]
	x = quick_sort(x)
	y = quick_sort(y)
	if m < n:
		z = x
		x = y
		y = z
		l = n
		n = m
		m = l
	koefy = 1
	koefx = 1
	i = m - 1
	j = n - 1
	answer = 0
	while i > -1 or j > -1:
		answer %= constmod
		if i == -1:
			answer += x[j] * koefx
			koefy += 1
			j -= 1
			continue
		if j == -1:
			answer += y[i] * koefy
			koefx += 1
			i -= 1
			continue
		if y[i] >= x[j]:
			answer += y[i] * koefy
			koefx += 1
			i -= 1
			continue
		else:
			answer += x[j] * koefx
			koefy += 1
			j -= 1
			continue
	answer %= constmod
	print(answer)


def solve(x, y, hcuts, vcuts):
	m = None
	for (i, e) in enumerate(x):
		cost = e * hcuts + solve(x[:i] + x[i + 1:], y, hcuts, vcuts + 1)
		m = cost if m is None else min(m, cost)
	for (i, e) in enumerate(y):
		cost = e * vcuts + solve(x, y[:i] + y[i + 1:], hcuts + 1, vcuts)
		m = cost if m is None else min(m, cost)
	return m if m is not None else 0
for case in range(int(input())):
	(M, N) = map(int, input().split())
	Y = list(map(int, input().split()))
	X = list(map(int, input().split()))
	Y.sort(reverse=True)
	X.sort(reverse=True)
	(hcuts, vcuts) = (1, 1)
	cost = 0
	while len(Y) and len(X):
		if X[0] >= Y[0]:
			cost += X.pop(0) * hcuts
			vcuts += 1
		else:
			cost += Y.pop(0) * vcuts
			hcuts += 1
		cost = cost % 1000000007
	while len(X):
		cost += X.pop(0) * hcuts
		cost = cost % 1000000007
	while len(Y):
		cost += Y.pop(0) * vcuts
		cost = cost % 1000000007
	print(cost)


modulo = 10 ** 9 + 7
for t in range(int(input())):
	(m, n) = [int(i) for i in input().split()]
	x = sorted(list(map(int, input().split())))
	y = sorted(list(map(int, input().split())))
	xParts = yParts = 1
	cost = 0
	for cut in range(n + m - 2):
		xMax = x[-1] if len(x) else -1
		yMax = y[-1] if len(y) else -1
		if xMax > yMax:
			cost = (cost + xMax * yParts) % modulo
			x.pop()
			xParts += 1
		else:
			cost = (cost + yMax * xParts) % modulo
			y.pop()
			yParts += 1
	print(cost)


modc = 1000000007
t = int(input())
for _ in range(t):
	(M, N) = list(map(int, input().split()))
	x = list(map(lambda v: (int(v), 0), input().split()))
	y = list(map(lambda v: (int(v), 1), input().split()))
	z = sorted(x + y, reverse=True)
	cut = [1, 1]
	ans = 0
	for (v, o) in z:
		ans = (ans + v * cut[1 - o]) % modc
		cut[o] += 1
	print(ans)


Q = 10 ** 9 + 7
for _ in range(int(input())):
	(M, N) = map(int, input().split())
	y = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y.sort()
	x.sort()
	if x[-1] > y[-1]:
		z = x
		x = y
		y = z
	bill = 0
	ym = 1
	xm = 1
	while len(x) > 0 and len(y) > 0:
		if y[-1] > x[-1]:
			bill = (bill + y.pop() * ym) % Q
			xm += 1
		else:
			bill = (bill + x.pop() * xm) % Q
			ym += 1
	for i in y:
		bill = (bill + i * ym) % Q
	for i in x:
		bill = (bill + i * xm) % Q
	print(bill)


import sys
from heapq import *

def inp():
	return list(map(int, input().split()))
M = 10 ** 9 + 7
print(M, file=sys.stderr)
t = int(input())
for _ in range(t):
	(m, n) = inp()
	y = inp()
	x = inp()
	h = []
	for i in y:
		heappush(h, (-i, 0))
	for i in x:
		heappush(h, (-i, 1))
	c = [1, 1]
	ans = 0
	while len(h) > 0:
		tmp = heappop(h)
		if tmp[1] == 0:
			ans += -tmp[0] * c[0]
			c[1] += 1
		else:
			ans += -tmp[0] * c[1]
			c[0] += 1
		ans %= M
	print(ans)


numinputs = int(input())
for dumm in range(numinputs):
	[m, n] = [int(val) for val in input().split()]
	x = [int(val) for val in input().split()]
	y = [int(val) for val in input().split()]
	cost = 0
	v = 1
	h = 1
	comb = []
	for val in x:
		comb.append((val, 'hor'))
	for val in y:
		comb.append((val, 'ver'))
	comb = sorted(comb, key=lambda x: x[0], reverse=True)
	for val in comb:
		if val[1] == 'hor':
			cost = (cost + val[0] * v) % 1000000007
			h += 1
		else:
			cost = (cost + val[0] * h) % 1000000007
			v += 1
	print(cost)


testcases = int(input())
for test in range(testcases):
	(m, n) = [int(i) for i in input().split()]
	m -= 2
	n -= 2
	ycut = sorted([int(i) for i in input().split()])
	xcut = sorted([int(i) for i in input().split()])
	assert len(ycut) >= 1
	assert len(xcut) >= 1
	xy = [1, 1]
	cost = 0
	while m >= 0 or n >= 0:
		if n >= 0 and m >= 0 and (xcut[n] > ycut[m]):
			choice = xcut[n]
			xcut[n] = 0
			n -= 1
			mode = 1
		elif m >= 0:
			assert m >= 0
			choice = ycut[m]
			ycut[m] = 0
			m -= 1
			mode = 0
		elif n >= 0:
			choice = xcut[n]
			xcut[n] = 0
			n -= 1
			mode = 1
		else:
			print('ERROR')
		cost += choice * xy[mode]
		xy[mode - 1] += 1
	print(cost % 1000000007)


def get_testcase():
	(_, _) = map(int, input().split())
	Y = list(map(int, input().split()))
	X = list(map(int, input().split()))
	return (X, Y)

def board_cutting(X, Y):
	prices = [(price, 0) for price in X] + [(price, 1) for price in Y]
	prices.sort(reverse=True)
	cost = 0
	counters = [1, 1]
	for (price, direction) in prices:
		cost += price * counters[1 - direction]
		counters[direction] += 1
	return cost
T = int(input())
for _ in range(T):
	(X, Y) = get_testcase()
	result = board_cutting(X, Y) % (10 ** 9 + 7)
	print(result)


MOD = 10 ** 9 + 7

def solve(X, Y):
	X.sort(reverse=True)
	Y.sort(reverse=True)
	(x, y, s) = (0, 0, 0)
	while x < len(X) and y < len(Y):
		if X[x] > Y[y]:
			s += (y + 1) * X[x] % MOD
			x += 1
		else:
			s += (x + 1) * Y[y] % MOD
			y += 1
	while x < len(X):
		s += (y + 1) * X[x] % MOD
		x += 1
	while y < len(Y):
		s += (x + 1) * Y[y] % MOD
		y += 1
	return s % MOD
T = int(input())
for _ in range(T):
	(M, N) = (int(_) for _ in input().split())
	X = [int(_) for _ in input().split()]
	Y = [int(_) for _ in input().split()]
	print(solve(X, Y))


cases = []
for i in range(int(input())):
	(_, _) = [int(i) for i in input().split()]
	Y = [int(i) for i in input().split()]
	X = [int(i) for i in input().split()]
	cases.append((Y, X))
for case in cases:
	Y = case[0]
	X = case[1]
	Y.sort(reverse=True)
	X.sort(reverse=True)
	sum = 0
	Ysum = [0 for _ in Y]
	i = len(Y) - 1
	while i >= 0:
		sum += Y[i]
		Ysum[i] = sum
		i -= 1
	sum = 0
	Xsum = [0 for _ in X]
	i = len(X) - 1
	while i >= 0:
		sum += X[i]
		Xsum[i] = sum
		i -= 1
	i = 0
	j = 0
	sum = 0
	while i < len(Y) or j < len(X):
		if i == len(Y):
			sum += X[j] * (i + 1)
			j += 1
		elif j == len(X):
			sum += Y[i] * (j + 1)
			i += 1
		elif X[j] > Y[i]:
			sum += X[j] * (i + 1)
			j += 1
		else:
			sum += Y[i] * (j + 1)
			i += 1
	print(sum % (10 ** 9 + 7))


cases = []
for i in range(int(input())):
	(_, _) = [int(i) for i in input().split()]
	Y = [int(i) for i in input().split()]
	X = [int(i) for i in input().split()]
	cases.append((Y, X))
for case in cases:
	Y = case[0]
	X = case[1]
	Y.sort(reverse=True)
	X.sort(reverse=True)
	i = 0
	j = 0
	sum = 0
	while i < len(Y) or j < len(X):
		if i == len(Y):
			sum += X[j] * (i + 1)
			j += 1
		elif j == len(X):
			sum += Y[i] * (j + 1)
			i += 1
		elif X[j] > Y[i]:
			sum += X[j] * (i + 1)
			j += 1
		else:
			sum += Y[i] * (j + 1)
			i += 1
	print(sum % (10 ** 9 + 7))


T = int(input())
for t in range(0, T):
	line = [int(z) for z in input().split()]
	M = line[0]
	N = line[1]
	verti = sorted([int(z) for z in input().split()], reverse=True)
	hori = sorted([int(z) for z in input().split()], reverse=True)
	(v, h) = (0, 0)
	total = 0
	while v + h < M * N:
		if v >= len(verti):
			while h < len(hori):
				total += (v + 1) * hori[h]
				h += 1
			break
		if h >= len(hori):
			while v < len(verti):
				total += (h + 1) * verti[v]
				v += 1
			break
		if verti[v] > hori[h]:
			total += (h + 1) * verti[v]
			v += 1
		else:
			total += (v + 1) * hori[h]
			h += 1
	print(total % (10 ** 9 + 7))


for T in range(int(input())):
	(M, N) = map(int, input().split())
	h = [(int(i), 0) for i in input().split()] + [(int(i), 1) for i in input().split()]
	(mod, p, ans) = (1000000007, [1, 1], 0)
	for i in sorted(h, reverse=True):
		ans = (ans + i[0] * p[1 - i[1]] % mod) % mod
		p[i[1]] += 1
	print(ans)


def min_cost(xs, ys):
	merged = [(x, 'h') for x in xs]
	merged.extend(((y, 'v') for y in ys))
	merged.sort(reverse=True)
	h = v = 0
	cost = 0
	for (el, t) in merged:
		if t == 'h':
			cost += el * (v + 1)
			h += 1
		else:
			cost += el * (h + 1)
			v += 1
	return cost % (10 ** 9 + 7)
n = int(input())
for _ in range(n):
	input()
	xs = [int(el) for el in input().split()]
	ys = [int(el) for el in input().split()]
	print(min_cost(xs, ys))


T = int(input())
for t in range(T):
	[M, N] = list(map(int, input().split()))
	y = sorted(list(map(int, input().split())))
	x = sorted(list(map(int, input().split())))
	total_cost = 0
	horizontal_cuts = 0
	vertical_cuts = 0
	for i in range(len(y) + len(x)):
		maxy = -1
		maxx = -1
		if vertical_cuts < len(y):
			maxy = y[-vertical_cuts - 1]
		if horizontal_cuts < len(x):
			maxx = x[-horizontal_cuts - 1]
		if maxy > maxx:
			total_cost += (horizontal_cuts + 1) * maxy
			vertical_cuts += 1
		elif maxx > maxy:
			total_cost += (vertical_cuts + 1) * maxx
			horizontal_cuts += 1
		elif (horizontal_cuts + 1) * maxy + (vertical_cuts + 2) * maxx > (horizontal_cuts + 2) * maxy + (vertical_cuts + 1) * maxx:
			total_cost += (vertical_cuts + 1) * maxx
			horizontal_cuts += 1
		elif (horizontal_cuts + 1) * maxy + (vertical_cuts + 2) * maxx <= (horizontal_cuts + 2) * maxy + (vertical_cuts + 1) * maxx:
			total_cost += (horizontal_cuts + 1) * maxy
			vertical_cuts += 1
	tt = total_cost % (10 ** 9 + 7)
	print(tt)


def cutBoard(m, n, x, y):
	x.sort()
	y.sort()
	(x_segs, y_segs) = [1, 1]
	cost = 0
	while y_segs < m or x_segs < n:
		if y_segs < m and x_segs < n:
			if y[m - y_segs - 1] >= x[n - x_segs - 1]:
				cut_y = True
			else:
				cut_y = False
		elif y_segs < m:
			cut_y = True
		else:
			cut_y = False
		if cut_y:
			cost += y.pop() * x_segs
			y_segs += 1
		else:
			cost += x.pop() * y_segs
			x_segs += 1
	return cost % (pow(10, 9) + 7)
cases = int(input())
for c in range(cases):
	(m, n) = [int(x) for x in input().strip().split()]
	y = [int(x) for x in input().strip().split()]
	x = [int(x) for x in input().strip().split()]
	print(cutBoard(m, n, x, y))


t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	x = sorted([int(i) for i in input().split()], reverse=True)
	y = sorted([int(i) for i in input().split()], reverse=True)
	segX = 1
	segY = 1
	cost = 0
	while len(x) > 0 or len(y) > 0:
		if len(x) > 0 and len(y) > 0:
			if x[0] > y[0]:
				cost += x[0] * segY
				segX += 1
				del x[0]
			else:
				cost += y[0] * segX
				segY += 1
				del y[0]
		elif len(x) > 0:
			cost += x[0] * segY
			segX += 1
			del x[0]
		else:
			cost += y[0] * segX
			segY += 1
			del y[0]
	print(cost % (10 ** 9 + 7))


M = 10 ** 9 + 7
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	ans = i = j = 0
	while i < len(a) and j < len(b):
		if a[i] > b[j]:
			ans += a[i] * (j + 1)
			i += 1
		else:
			ans += b[j] * (i + 1)
			j += 1
	while i < len(a):
		ans += a[i] * (j + 1)
		i += 1
	while j < len(b):
		ans += b[j] * (i + 1)
		j += 1
	print(ans % M)


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	lm = list(map(int, input().split()))
	ln = list(map(int, input().split()))
	lm.sort(reverse=True)
	ln.sort(reverse=True)
	cm = cn = 1
	res = 0
	while ln or lm:
		if not ln or (lm and lm[0] > ln[0]):
			res += lm[0] * cn
			lm.pop(0)
			cm += 1
		else:
			res += ln[0] * cm
			ln.pop(0)
			cn += 1
		res %= 10 ** 9 + 7
	print(res)


def minimal_cost(L1, L2):
	(i, j) = (0, 0)
	(H, V) = (1, 1)
	total = 0
	while i < len(L1) and j < len(L2):
		if L1[i] >= L2[j]:
			total += H * L1[i]
			i += 1
			V += 1
		else:
			total += V * L2[j]
			j += 1
			H += 1
	while i < len(L1):
		total += H * L1[i]
		i += 1
		V += 1
	while j < len(L2):
		total += V * L2[j]
		j += 1
		H += 1
	return total % (10 ** 9 + 7)
numTrials = int(input())
for i in range(numTrials):
	k = input()
	L1 = input().split()
	L1 = sorted([int(i) for i in L1], reverse=True)
	L2 = input().split()
	L2 = sorted([int(i) for i in L2], reverse=True)
	print(minimal_cost(L1, L2))


moduloDivisor = 10 ** 9 + 7
t = int(input())
for testNum in range(0, t):
	(m, n) = list(map(int, input().split()))
	verts = sorted(list(map(int, input().split())), reverse=True)
	horizs = sorted(list(map(int, input().split())), reverse=True)
	ans = 0
	rows = 1
	clmns = 1
	while verts or horizs:
		if verts and (not horizs or verts[0] > horizs[0]):
			clmns += 1
			ans += verts.pop(0) * rows
		else:
			rows += 1
			ans += horizs.pop(0) * clmns
	ans %= moduloDivisor
	print(ans)


t = int(input())
c = 0
while c < t:
	c += 1
	[x, y] = [int(x) for x in input().split(' ')]
	if x > 2:
		xvals = sorted([int(x) for x in input().split(' ')], key=lambda x: -x)
	else:
		xvals = [int(input())]
	if y > 2:
		yvals = sorted([int(x) for x in input().split(' ')], key=lambda x: -x)
	else:
		yvals = [int(input())]
	mval = 10 ** 9 + 7
	yvals.append(0)
	xvals.append(0)
	yidx = xidx = 0
	cost = 0
	while yidx < len(yvals) and xidx < len(xvals):
		if yvals[yidx] < xvals[xidx]:
			cost += xvals[xidx] * (yidx + 1)
			xidx += 1
		else:
			cost += yvals[yidx] * (xidx + 1)
			yidx += 1
		cost %= mval
	print(cost)


def MinimalCost(X, Y, M, N):
	modulo = 1000000007
	Y.sort(reverse=True)
	X.sort(reverse=True)
	(i, j) = (0, 0)
	totalCost = 0
	HorizontalCut = 1
	VerticalCut = 1
	while i < N - 1 or j < M - 1:
		if i < N - 1 and (j >= M - 1 or X[i] > Y[j]):
			totalCost += X[i] * HorizontalCut
			i += 1
			VerticalCut += 1
		elif i >= N - 1 or X[i] <= Y[j]:
			totalCost += Y[j] * VerticalCut
			j += 1
			HorizontalCut += 1
	return totalCost % modulo
T = int(input())
for _ in range(0, T):
	(M, N) = map(int, input().split())
	Y = list(map(int, input().split()))
	X = list(map(int, input().split()))
	print(MinimalCost(X, Y, M, N))


t = int(input())
for _ in range(t):
	(m, n) = map(lambda x: int(x) - 1, input().split())
	L = sorted(list(map(int, input().split())), reverse=True)
	C = sorted(list(map(int, input().split())), reverse=True)
	(l, c, i, j, s) = (1, 1, 0, 0, 0)
	while i < m and j < n:
		if L[i] > C[j]:
			s += L[i] * c
			l += 1
			i += 1
		else:
			s += C[j] * l
			c += 1
			j += 1
	while i < m:
		s += L[i] * c
		l += 1
		i += 1
	while j < n:
		s += C[j] * l
		c += 1
		j += 1
	print(s % 1000000007)


import sys

def cum_sum(xs):
	sum_ = 0
	result = list()
	for x in xs:
		sum_ += x
		result.append(sum_)
	return result

def solve(xs, ys):
	cum_xs = cum_sum(xs)
	cum_ys = cum_sum(ys)
	ans = 0
	while xs or ys:
		if not xs:
			return ans + cum_ys.pop()
		if not ys:
			return ans + cum_xs.pop()
		if xs[-1] >= ys[-1]:
			cum_xs.pop()
			ans += xs.pop() + cum_ys[-1]
		else:
			cum_ys.pop()
			ans += ys.pop() + cum_xs[-1]
T = int(sys.stdin.readline())
for case in range(T):
	sys.stdin.readline()
	ys = sorted([int(y) for y in sys.stdin.readline().split()])
	xs = sorted([int(x) for x in sys.stdin.readline().split()])
	ans = solve(xs, ys)
	print(ans % 1000000007)


t = int(input())
for _ in range(t):
	cost = 0
	(m, n) = list(map(int, input().strip().split(' ')))
	horz = list(map(int, input().strip().split(' ')))
	vert = list(map(int, input().strip().split(' ')))
	horz_pieces = 1
	vert_pieces = 1
	horz.sort(reverse=True)
	vert.sort(reverse=True)
	horz_index = 0
	vert_index = 0
	while horz_index < len(horz) and vert_index < len(vert):
		if horz[horz_index] > vert[vert_index]:
			vert_pieces += 1
			cost += horz_pieces * horz[horz_index]
			horz_index += 1
		elif horz[horz_index] < vert[vert_index]:
			horz_pieces += 1
			cost += vert_pieces * vert[vert_index]
			vert_index += 1
		elif horz_pieces > vert_pieces:
			vert_pieces += 1
			cost += horz_pieces * horz[horz_index]
			horz_index += 1
		else:
			horz_pieces += 1
			cost += vert_pieces * vert[vert_index]
			vert_index += 1
	while horz_index < len(horz):
		vert_pieces += 1
		cost += horz_pieces * horz[horz_index]
		horz_index += 1
	while vert_index < len(vert):
		horz_pieces += 1
		cost += vert_pieces * vert[vert_index]
		vert_index += 1
	cost = cost % (10 ** 9 + 7)
	print(cost)


T = int(input())
for t in range(T):
	(M, N) = tuple(map(int, input().split()))
	X = sorted(list(map(int, input().split())))
	Y = sorted(list(map(int, input().split())))
	x_num = 1
	y_num = 1
	out = 0
	while X or Y:
		if not X:
			out += x_num * Y[-1]
			Y.pop()
			y_num += 1
		elif not Y:
			out += y_num * X[-1]
			X.pop()
			x_num += 1
		elif X[-1] <= Y[-1]:
			out += x_num * Y[-1]
			Y.pop()
			y_num += 1
		elif X[-1] > Y[-1]:
			out += y_num * X[-1]
			X.pop()
			x_num += 1
		else:
			print('?')
	print(out % (10 ** 9 + 7))


T = int(input())
for t in range(0, T):
	var = input().split()
	(M, N) = (int(var[0]), int(var[1]))
	arr_M = []
	arr_N = []
	var = input().split()
	for i in range(0, M - 1):
		arr_M.append(int(var[i]))
	var = input().split()
	for i in range(0, N - 1):
		arr_N.append(int(var[i]))
	arr_M.sort(reverse=True)
	arr_N.sort(reverse=True)
	cost = 0
	m_idx = n_idx = 0
	while n_idx + m_idx < N - 1 + M - 1:
		if m_idx < M - 1 and n_idx < N - 1:
			if arr_M[m_idx] > arr_N[n_idx]:
				cost += arr_M[m_idx] * (n_idx + 1)
				m_idx += 1
			else:
				cost += arr_N[n_idx] * (m_idx + 1)
				n_idx += 1
		elif m_idx < M - 1:
			cost += arr_M[m_idx] * (n_idx + 1)
			m_idx += 1
		else:
			cost += arr_N[n_idx] * (m_idx + 1)
			n_idx += 1
	print(cost % (10 ** 9 + 7))


def board_cutting(M, N, Y, X):
	C = sorted(X + Y, reverse=True)
	(T, V, H) = (0, 0, 0)
	for i in range(M + N - 2):
		if C[i][1]:
			T += C[i][0] * (V + 1)
			T %= 1000000007
			H += 1
		else:
			T += C[i][0] * (H + 1)
			T %= 1000000007
			V += 1
	return T

def main():
	T = int(input())
	for _ in range(T):
		(M, N) = [int(i) for i in input().split()]
		Y = [(int(y), 1) for y in input().split()]
		X = [(int(x), 0) for x in input().split()]
		print(board_cutting(M, N, Y, X))
main()


MOD = 10 ** 9 + 7

def solve(Mval, Nval, yarr, xarr):
	yarr.sort()
	ysum = sum(yarr)
	xarr.sort()
	xsum = sum(xarr)
	(xval, yval) = (0, 0)
	total = 0
	while yarr and xarr:
		yval = yarr[-1]
		xval = xarr[-1]
		if yval > xval:
			total += yarr.pop() * (Nval - len(xarr))
			ysum -= yval
		elif xval > yval:
			total += xarr.pop() * (Mval - len(yarr))
			xsum -= yval
		elif ysum > xsum:
			total += yarr.pop() * (Nval - len(xarr))
			xsum -= xval
		else:
			total += xarr.pop() * (Mval - len(yarr))
	while yarr:
		total += yarr.pop() * (Nval - len(xarr))
	while len(xarr) > 0:
		total += xarr.pop() * (Mval - len(yarr))
	return total % MOD
for _ in range(int(input())):
	(nval, mval) = list(map(int, input().split()))
	yarr = list(map(int, input().split()))
	xarr = list(map(int, input().split()))
	print(solve(nval, mval, yarr, xarr))


T = int(input())
for i in range(0, T):
	(m, n) = map(int, input().split())
	yi = list(map(int, input().split()))
	xi = list(map(int, input().split()))
	yi = sorted(yi)[::-1]
	xi = sorted(xi)[::-1]
	ny = 1
	nx = 1
	c = 0
	while ny < m or nx < n:
		if ny < m and (nx >= n or yi[ny - 1] > xi[nx - 1]):
			c = (c + nx * yi[ny - 1] % 1000000007) % 1000000007
			ny += 1
		elif nx < n and (ny >= m or xi[nx - 1] >= yi[ny - 1]):
			c = (c + ny * xi[nx - 1] % 1000000007) % 1000000007
			nx += 1
	print(c)


MOD = 10 ** 9 + 7
ncases = int(input())
for _ in range(ncases):
	(m, n) = [int(fld) for fld in input().split()]
	hcost = [int(fld) for fld in input().split()]
	vcost = [int(fld) for fld in input().split()]
	assert len(hcost) == m - 1 and len(vcost) == n - 1
	cost = [(c, 0) for c in hcost] + [(c, 1) for c in vcost]
	cost.sort(reverse=True)
	assert all((c1[0] >= c2[0] for (c1, c2) in zip(cost, cost[1:])))
	total = 0
	cuts = [0, 0]
	for (c, kind) in cost:
		total += c * (1 + cuts[1 - kind])
		cuts[kind] += 1
	print(total % MOD)


t = int(input())
for i in range(t):
	temp = input().split(' ')
	m = int(temp[0])
	n = int(temp[1])
	temp = input().split(' ')
	y = []
	temp_maxy = []
	for i in range(m - 1):
		y.append(int(temp[i]))
		temp_maxy.append(int(temp[i]))
	x = []
	temp_maxx = []
	temp = input().split(' ')
	for i in range(n - 1):
		x.append(int(temp[i]))
		temp_maxx.append(int(temp[i]))
	temp_maxx.sort(reverse=True)
	temp_maxy.sort(reverse=True)
	cost = 0
	xpart = 1
	ypart = 1
	i = 0
	j = 0
	while i < m - 1 and j < n - 1:
		if temp_maxy[i] >= temp_maxx[j]:
			cost = cost + xpart * temp_maxy[i]
			ypart = ypart + 1
			i = i + 1
		else:
			cost = cost + ypart * temp_maxx[j]
			xpart = xpart + 1
			j = j + 1
	if i == m - 1:
		while j < n - 1:
			cost = cost + ypart * temp_maxx[j]
			xpart = xpart + 1
			j = j + 1
	if j == n - 1:
		while i < m - 1:
			cost = cost + xpart * temp_maxy[i]
			ypart = ypart + 1
			i = i + 1
	print(cost % (10 ** 9 + 7))


T = int(input())
for i in range(T):
	[M, N] = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	[xCuts, yCuts] = [1, 1]
	tCost = 0
	x.append(-1)
	y.append(-1)
	x.sort()
	y.sort()
	while x[-1] != -1 or y[-1] != -1:
		if x[-1] > y[-1]:
			tCost = tCost + yCuts * x.pop()
			if y[-1] != -1:
				xCuts = xCuts + 1
		else:
			tCost = tCost + xCuts * y.pop()
			if x[-1] != -1:
				yCuts = yCuts + 1
	print(tCost % (10 ** 9 + 7))


tests = int(input())
for _ in range(tests):
	(n, m) = map(int, input().split())
	y = sorted([int(a) for a in input().split()])
	x = sorted([int(a) for a in input().split()])
	cost = 0
	x_seg = 1
	y_seg = 1
	while x or y:
		if x and (not y or x[-1] > y[-1]):
			cost += x[-1] * y_seg
			x_seg += 1
			del x[-1]
		else:
			cost += y[-1] * x_seg
			y_seg += 1
			del y[-1]
	print(cost % (10 ** 9 + 7))


from sys import stdin
t = int(stdin.readline())
modulus = 10 ** 9 + 7
for _ in range(0, t):
	(n, m) = stdin.readline().split()
	r = [int(x) for x in stdin.readline().split()]
	c = [int(x) for x in stdin.readline().split()]
	r.sort()
	c.sort()
	nc = 1
	nr = 1
	s = 0
	while len(r) > 0 or len(c) > 0:
		if len(c) == 0 or (len(r) > 0 and r[-1] > c[-1]):
			s += nr * r[-1]
			r.pop()
			nc += 1
		else:
			s += nc * c[-1]
			c.pop()
			nr += 1
	print(s % modulus)


T = int(input())
for t in range(T):
	(M, N) = map(int, input().split())
	y = [int(a) for a in input().split()]
	x = [int(a) for a in input().split()]
	y.sort()
	x.sort()
	nh = 1
	nv = 1
	cost = 0
	while len(x) or len(y):
		mh = -1
		mv = -1
		if len(y):
			mh = y[len(y) - 1]
		if len(x):
			mv = x[len(x) - 1]
		if (mh > mv or (mh == mv and M > N)) or mv == -1:
			cost = cost + nh * mh
			y.pop()
			nv = nv + 1
		else:
			cost = cost + nv * mv
			x.pop()
			nh = nh + 1
	print(cost % 1000000007)


def merge(s1, s2):
	i = j = 0
	x = y = 1
	ans = 0
	while i + j < len(s1) + len(s2):
		if j == len(s2) or (i < len(s1) and s1[i] > s2[j]):
			ans += s1[i] * x
			i += 1
			y += 1
		else:
			ans += s2[j] * y
			j += 1
			x += 1
	return ans
t = int(input())
for yy in range(t):
	inf = list(map(int, input().split()))
	h = inf[0]
	v = inf[1]
	y = 1
	x = 1
	hor = list(map(int, input().split()))
	ver = list(map(int, input().split()))
	ver = sorted(ver, reverse=True)
	hor = sorted(hor, reverse=True)
	f = 0
	p = 0
	ans = 0
	if len(ver) < len(hor):
		one = hor
		two = ver
	else:
		one = ver
		two = hor
	ans = merge(one, two)
	print(ans % (10 ** 9 + 7))


mod = 1000000007
for _ in range(int(input())):
	(m, n) = [int(i) for i in input().strip().split()]
	Y = [(int(i), True) for i in input().strip().split()]
	X = [(int(i), False) for i in input().strip().split()]
	F = sorted(X + Y, reverse=True)
	cost = 0
	dy = 1
	dx = 1
	for (c, group) in F:
		if group:
			cost = (cost + c * dy) % mod
			dx += 1
		else:
			cost = (cost + c * dx) % mod
			dy += 1
	print(cost)


MAX = 1000000007
T = int(input())
for i in range(T):
	(M, N) = map(int, input().strip().split())
	y = list(map(int, input().strip().split()))
	x = list(map(int, input().strip().split()))
	y = sorted(y, reverse=True)
	x = sorted(x, reverse=True)
	hor = 0
	ver = 0
	cut = 0
	while ver < M - 1 and hor < N - 1:
		if x[hor] > y[ver]:
			cut = cut + x[hor] * (ver + 1) % MAX
			hor += 1
		else:
			cut = cut + y[ver] * (hor + 1) % MAX
			ver += 1
	cut = cut + (ver + 1) * sum([x[j] for j in range(hor, N - 1)]) % MAX
	cut = cut + (hor + 1) * sum([y[j] for j in range(ver, M - 1)]) % MAX
	print(cut % MAX)


from itertools import chain
T = int(input())
MOD = 10 ** 9 + 7
for test_case in range(T):
	(M, N) = [int(x) for x in input().strip().split()]
	x = sorted([int(x) for x in input().strip().split()])
	y = sorted([int(x) for x in input().strip().split()])
	x_cuts = 1
	y_cuts = 1
	cost = 0
	while x or y:
		if x and y:
			greedy_cut = max(x[-1], y[-1])
		elif x:
			greedy_cut = x[-1]
		else:
			greedy_cut = y[-1]
		if x and greedy_cut == x[-1]:
			cost += y_cuts * greedy_cut % MOD
			x.pop()
			x_cuts += 1
		else:
			cost += x_cuts * greedy_cut % MOD
			y.pop()
			y_cuts += 1
	print(cost % MOD)


cases = int(input())
for test in range(cases):
	[m, n] = list(map(int, input().split()))
	costY = sorted(list(map(int, input().split())), reverse=True)
	costX = sorted(list(map(int, input().split())), reverse=True)
	x = 1
	y = 1
	cost = 0
	while y < m and x < n:
		if costX[0] > costY[0]:
			cost += y * costX[0]
			x += 1
			del costX[0]
		else:
			cost += x * costY[0]
			y += 1
			del costY[0]
	if costX == []:
		cost += n * sum(costY)
	else:
		cost += m * sum(costX)
	print(cost % 1000000007)


def cutter(ar, y, x):
	counter_x = 1
	counter_y = 1
	cost = 0
	x.sort()
	x.reverse()
	y.sort()
	y.reverse()
	(i, j) = (0, 0)
	while i < len(y):
		while j < len(x) and x[j] >= y[i]:
			if x[j] == y[i] and counter_y < counter_x:
				cost += x[j] * counter_y
				counter_x += 1
				j += 1
			elif x[j] != y[i]:
				cost += x[j] * counter_y
				counter_x += 1
				j += 1
			else:
				break
		cost += y[i] * counter_x
		counter_y += 1
		i += 1
	if i < len(y):
		while i < len(y):
			cost += y[i] * counter_x
			i += 1
	if j < len(x):
		while j < len(x):
			cost += x[j] * counter_y
			j += 1
	return cost % (10 ** 9 + 7)
for n in range(int(input())):
	ar = list(map(int, input().split()))
	y = list(map(int, input().split()))
	x = list(map(int, input().split()))
	print(cutter(ar, y, x))


T = int(input())
for i in range(T):
	(M, N) = map(int, input().split())
	y = sorted(map(int, input().split()), reverse=True)
	x = sorted(map(int, input().split()), reverse=True)
	m = 0
	n = 0
	c = 0
	while True:
		if m >= M - 1 and n >= N - 1:
			break
		if n >= N - 1 or (m < M - 1 and y[m] > x[n]):
			c += (n + 1) * y[m]
			m += 1
		else:
			c += (m + 1) * x[n]
			n += 1
	print(c % (10 ** 9 + 7))


import heapq
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	y = list(map(int, input().split()))
	x = list(map(int, input().split()))
	x.sort(reverse=True)
	y.sort(reverse=True)
	px = 0
	py = 0
	h = 1
	v = 1
	ans = 0
	while py < m - 1 or px < n - 1:
		if py < m - 1 and px < n - 1:
			if y[py] > x[px]:
				ans = ans + y[py] * v
				py = py + 1
				h = h + 1
			elif y[py] < x[px]:
				ans = ans + x[px] * h
				v = v + 1
				px = px + 1
			elif v < h:
				ans = ans + y[py] * v
				py = py + 1
				h = h + 1
			else:
				ans = ans + x[px] * h
				v = v + 1
				px = px + 1
		elif px < n - 1:
			ans = ans + x[px] * h
			v = v + 1
			px = px + 1
		else:
			ans = ans + y[py] * v
			py = py + 1
			h = h + 1
	print(ans % 1000000007)


test_num = int(input())
for test in range(0, test_num):
	(col, rows) = [int(i) - 1 for i in input().split()]
	hor_cost = [int(i) for i in input().split()]
	hor_cost.sort(reverse=True)
	ver_cost = [int(i) for i in input().split()]
	ver_cost.sort(reverse=True)
	h = 1
	v = 1
	total = 0
	for i in range(0, col + rows):
		if hor_cost != [] and ver_cost != []:
			if hor_cost[0] > ver_cost[0]:
				cost = hor_cost.pop(0)
				total += cost * v
				h += 1
			else:
				cost = ver_cost.pop(0)
				total += cost * h
				v += 1
		elif hor_cost != []:
			cost = hor_cost.pop(0)
			total += cost * v
			h += 1
		else:
			cost = ver_cost.pop(0)
			total += cost * h
			v += 1
	print(total % 1000000007)


t = int(input())
for _ in range(t):
	(x, y) = [int(i) for i in input().split()]
	xCost = [int(i) for i in input().split()]
	yCost = [int(i) for i in input().split()]
	xCost.append(-1)
	yCost.append(-1)
	cost = 0
	xCost.sort()
	yCost.sort()
	xCost.reverse()
	yCost.reverse()
	xCount = 1
	yCount = 1
	while len(xCost) > 1 or len(yCost) > 1:
		if xCost[0] >= yCost[0]:
			cost += xCost[0] * yCount
			xCount += 1
			xCost.pop(0)
		else:
			cost += yCost[0] * xCount
			yCount += 1
			yCost.pop(0)
	print(cost % (10 ** 9 + 7))


def quickSort(array, left, right):
	if left < right:
		p = partition(array, left, right)
		quickSort(array, left, p - 1)
		quickSort(array, p + 1, right)

def partition(array, left, right):
	pivot = array[right]
	i = left - 1
	for j in range(left, right):
		if array[j] <= pivot:
			i += 1
			tmp = array[j]
			array[j] = array[i]
			array[i] = tmp
	array[right] = array[i + 1]
	array[i + 1] = pivot
	return i + 1

def optimalCut(m, n, y, x):
	if m < n:
		(m, n) = (n, m)
		(y, x) = (x, y)
	total = 0
	hPieces = 1
	vPieces = 1
	quickSort(y, 0, m - 2)
	quickSort(x, 0, n - 2)
	yIndex = m - 2
	xIndex = n - 2
	while yIndex >= 0 and xIndex >= 0:
		if y[yIndex] >= x[xIndex]:
			total += vPieces * y[yIndex]
			yIndex -= 1
			hPieces += 1
		else:
			total += hPieces * x[xIndex]
			xIndex -= 1
			vPieces += 1
	while yIndex >= 0:
		total += vPieces * y[yIndex]
		yIndex -= 1
		hPieces += 1
	while xIndex >= 0:
		total += hPieces * x[xIndex]
		xIndex -= 1
		vPieces += 1
	return total % (10 ** 9 + 7)
t = int(input())
for i in range(t):
	(m, n) = input().split()
	(m, n) = (int(m), int(n))
	y = input().split()
	y = [int(i) for i in y]
	x = input().split()
	x = [int(i) for i in x]
	print(optimalCut(m, n, y, x))


for t in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	y = [[int(x), 1, 0] for x in input().split()]
	x = [[int(z), 0, 1] for z in input().split()]
	z = x + y
	z.sort(key=lambda a: a[0])
	c1 = 1
	c2 = 1
	c = 0
	l = len(z)
	for i in range(l):
		c += z[l - 1 - i][0] * z[l - 1 - i][1] * c1 + z[l - 1 - i][0] * z[l - 1 - i][2] * c2
		c1 += z[l - 1 - i][2]
		c2 += z[l - 1 - i][1]
	print(c % 1000000007)


T = int(input())
for _ in range(T):
	(M, N) = tuple([int(x) for x in input().split()])
	ys = [(int(x), 1) for x in input().split()]
	xs = [(int(x), 0) for x in input().split()]
	xys = reversed(sorted(xs + ys))
	xy_so_far = [1, 1]
	total_cost = 0
	for (cost, xy_ind) in xys:
		total_cost += xy_so_far[1 - xy_ind] * cost
		xy_so_far[xy_ind] += 1
	print(total_cost % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(m, n) = input().split()
	(m, n) = (int(m), int(n))
	x = sorted([int(x) for x in input().split()], reverse=True)
	y = sorted([int(y) for y in input().split()], reverse=True)
	(nv, nh) = (1, 1)
	total = 0
	while len(x) + len(y) > 0:
		if len(y) == 0 or (len(x) > 0 and x[0] > y[0]):
			total += x.pop(0) * nh
			total %= 1000000007
			nv += 1
		else:
			total += y.pop(0) * nv
			total %= 1000000007
			nh += 1
	print(total)


t = int(input())
for m in range(t):
	(x, y) = map(int, input().split())
	a = [0] * 1000000
	b = [0] * 1000000
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	x = x - 1
	y = y - 1
	sum = 0
	c = 1
	d = 1
	i = j = 0
	while i < x and j < y:
		while i < x and j < y and (a[i] <= b[j]):
			sum = (sum + b[j] * c) % 1000000007
			j += 1
			d += 1
		while j < y and i < x and (a[i] >= b[j]):
			sum = (sum + a[i] * d) % 1000000007
			i += 1
			c += 1
	while j < y:
		sum = (sum + b[j] * c) % 1000000007
		j += 1
	while i < x:
		sum = (sum + a[i] * d) % 1000000007
		i += 1
	print(sum)


import math

def make_horizontal_cut(x, y, m, n):
	if len(y) == 0:
		return False
	if len(x) == 0:
		return True
	if y[-1] > x[-1]:
		return True
	if x[-1] > y[-1]:
		return False
	else:
		return m > n
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	y = sorted(map(int, input().split()))
	x = sorted(map(int, input().split()))
	h_cuts = 0
	v_cuts = 0
	cost = 0
	while len(x) > 0 or len(y) > 0:
		if make_horizontal_cut(x, y, m, n):
			cost += y.pop() * (v_cuts + 1)
			h_cuts += 1
		else:
			cost += x.pop() * (h_cuts + 1)
			v_cuts += 1
	truncated = int(cost % 1000000007)
	print(truncated)


MOD_NUM = 1000000000 + 7
T = int(input().strip())
for t in range(T):
	(m, n) = input().strip().split(' ')
	(m, n) = [int(m), int(n)]
	Y = input().strip().split(' ')
	Y = [(int(y), 'y') for y in Y]
	X = input().strip().split(' ')
	X = [(int(x), 'x') for x in X]
	A = Y
	for x in X:
		A.append(x)
	A.sort(key=lambda x: x[0])
	numcuts_x = 1
	numcuts_y = 1
	Cost = 0
	while A:
		temp = A.pop()
		if temp[1] == 'x':
			Cost = (Cost + temp[0] * numcuts_y) % MOD_NUM
			numcuts_x += 1
		else:
			Cost = (Cost + temp[0] * numcuts_x) % MOD_NUM
			numcuts_y += 1
	print(Cost)


import sys

def cut_board(arrm, arrn):
	arrm = sorted(arrm, reverse=True)
	arrn = sorted(arrn, reverse=True)
	arrm.append(-1)
	arrn.append(-1)
	cutm = 0
	cutn = 0
	cost = 0
	for i in range(len(arrm) + len(arrn) - 2):
		max_arrm = arrm[cutm]
		max_arrn = arrn[cutn]
		if max_arrm >= max_arrn:
			cost += max_arrm * (1 + cutn)
			cutm += 1
		else:
			cost += max_arrn * (1 + cutm)
			cutn += 1
	print(cost % 1000000007)
	return
t = int(input().strip())
for i in range(t):
	(n, m) = input().strip().split(' ')
	arrm = [int(at) for at in input().strip().split(' ')]
	arrn = [int(at) for at in input().strip().split(' ')]
	cut_board(arrm, arrn)


t = int(input().strip())
z = 10 ** 9 + 7
for j in range(t):
	(m, n) = [int(x) for x in input().strip().split()]
	y = [[int(x), 0] for x in input().strip().split()]
	x = [[int(x), 1] for x in input().strip().split()]
	y.extend(x)
	y.sort(reverse=True)
	h = 1
	v = 1
	c = 0
	for i in range(m + n - 2):
		if y[i][1] == 0:
			c = (c + v * y[i][0]) % z
			h = h + 1
		else:
			c = (c + h * y[i][0]) % z
			v = v + 1
	print(c)


T = int(input())
for T_i in range(T):
	(m, n) = [int(x) for x in input().split()]
	y = [int(x) for x in input().split()]
	y = sorted(y, reverse=True)
	x = [int(x) for x in input().split()]
	x = sorted(x, reverse=True)
	totalcost = 0
	ycuts = 1
	xcuts = 1
	while len(x) > 0 or len(y) > 0:
		if len(x) == 0:
			while len(y) > 0:
				cy = y[0]
				totalcost += cy * xcuts
				ycuts += 1
				del y[0]
		elif len(y) == 0:
			while len(x) > 0:
				cx = x[0]
				totalcost += cx * ycuts
				xcuts += 1
				del x[0]
		elif y[0] < x[0]:
			cx = x[0]
			totalcost += cx * ycuts
			xcuts += 1
			del x[0]
		else:
			cy = y[0]
			totalcost += cy * xcuts
			ycuts += 1
			del y[0]
		totalcost = totalcost % 1000000007
	print(totalcost)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	assert m >= 2 and m <= 1000000
	assert n >= 2 and n <= 1000000
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	x.sort(reverse=True)
	y.sort(reverse=True)
	(xc, yc) = (1, 1)
	total = 0
	while True:
		if not x and (not y):
			break
		elif not x:
			v = y.pop(0)
			cut = xc
		elif not y:
			v = x.pop(0)
			cut = yc
		elif x[0] > y[0]:
			v = x.pop(0)
			cut = yc
			xc += 1
		else:
			v = y.pop(0)
			cut = xc
			yc += 1
		total += v * cut
	print(total % 1000000007)


T = int(input())
for t in range(T):
	(m, n) = [int(x) for x in input().split()]
	costY = [int(x) for x in input().split()]
	costX = [int(x) for x in input().split()]
	costY.sort(reverse=True)
	costX.sort(reverse=True)
	totalCost = 0
	numHorizontal = 1
	numVertical = 1
	idxY = 0
	idxX = 0
	lenCostY = len(costY)
	lenCostX = len(costX)
	for i in range(lenCostY + lenCostX):
		cutVert = False
		cutHort = False
		if idxX >= lenCostX:
			cutHort = True
		elif idxY >= lenCostY:
			cutVert = True
		elif costY[idxY] < costX[idxX]:
			cutVert = True
		else:
			cutHort = True
		if cutVert:
			totalCost += costX[idxX] * numHorizontal
			numVertical += 1
			idxX += 1
		if cutHort:
			totalCost += costY[idxY] * numVertical
			numHorizontal += 1
			idxY += 1
	print(totalCost % (pow(10, 9) + 7))


t = int(input())
for i in range(t):
	(m, n) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a.sort(reverse=True)
	b.sort(reverse=True)
	am = 1
	bm = 1
	c = 0
	while a or b:
		if not b or (a and a[0] >= b[0]):
			c += am * a.pop(0)
			bm += 1
		else:
			c += bm * b.pop(0)
			am += 1
	print(c % 1000000007)


m = int(1000000000.0 + 7)
for _ in range(int(input())):
	input()
	l = list(map(lambda x: (int(x), True), input().split())) + list(map(lambda x: (int(x), False), input().split()))
	l.sort(reverse=True)
	cx = cy = 1
	cost = 0
	for (price, isY) in l:
		if isY:
			cost = (cost + cx * price) % m
			cy += 1
		else:
			cost = (cost + cy * price) % m
			cx += 1
	print(cost)


def modulo(num):
	return num % (10 ** 9 + 7)
T = int(input())
for _ in range(0, T):
	(M, N) = list(map(int, input().split()))
	M_cut = 1
	N_cut = 1
	M_list = list(map(int, input().split()))
	N_list = list(map(int, input().split()))
	M_list.sort()
	N_list.sort()
	cost = 0
	while M_list and N_list:
		m = M_list.pop()
		n = N_list.pop()
		if m > n:
			N_list.append(n)
			cost = modulo(cost + modulo(m * N_cut))
			M_cut += 1
		else:
			M_list.append(m)
			cost = modulo(cost + modulo(n * M_cut))
			N_cut += 1
	if M_list:
		for i in M_list:
			cost = modulo(cost + modulo(i * N_cut))
	if N_list:
		for i in N_list:
			cost = modulo(cost + modulo(i * M_cut))
	print(cost)


T = int(input())
for _ in range(T):
	input()
	Cx = sorted([int(c) for c in input().split()], reverse=True)
	Cy = sorted([int(c) for c in input().split()], reverse=True)
	xcuts = 1
	ycuts = 1
	xi = 0
	yi = 0
	cost = 0
	for _ in range(len(Cx) + len(Cy)):
		if yi >= len(Cy) or (xi < len(Cx) and Cx[xi] > Cy[yi]):
			cost += Cx[xi] * ycuts
			xcuts += 1
			xi += 1
		else:
			cost += Cy[yi] * xcuts
			ycuts += 1
			yi += 1
	print(cost % (10 ** 9 + 7))


t = int(input())
for test in range(t):
	(m, n) = map(int, input().split())
	ma = map(int, input().split())
	na = map(int, input().split())
	result = 0
	ma = sorted(ma)
	na = sorted(na)
	for cut in range(m - 1 + n - 1):
		minm = ma[-1] if ma else -1
		minn = na[-1] if na else -1
		if minn > minm:
			result += minn * (m - len(ma))
			na.pop()
		else:
			result += minm * (n - len(na))
			ma.pop()
	print(result % (10 ** 9 + 7))


def main():
	(n, k) = map(int, input().split())
	H = [(i, 0) for i in map(int, input().split())]
	V = [(i, 1) for i in map(int, input().split())]
	c = [1, 1]
	s = 0
	for (v, d) in sorted(H + V, reverse=True):
		c[d] += 1
		s = (s + v * c[not d]) % (10 ** 9 + 7)
	print(s)
for i in range(int(input())):
	main()


import math
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	x = input()
	y = input()
	if m < n:
		(m, n, x, y) = (n, m, y, x)
	z = sorted([int(q) + 0.2 for q in x.split()] + [int(q) + 0.1 for q in y.split()], reverse=True)
	(cost, xcuts, ycuts) = (0, 1, 1)
	for i in z:
		xy = round(i % 1, 1)
		cost += math.floor(i) * (ycuts if xy == 0.2 else xcuts)
		xcuts = xcuts + 1 if xy == 0.2 else xcuts
		ycuts = ycuts + 1 if xy == 0.1 else ycuts
	print(cost % (10 ** 9 + 7))


import sys

class Board:

	def __init__(self, mn, cy, cx):
		cy.insert(0, 0)
		cx.insert(0, 0)
		(self.m, self.n) = mn
		self.cy = cy
		self.cx = cx
		self.ccy = list(cy)
		self.ccx = list(cx)
		self.ry = set(range(1, self.m))
		self.rx = set(range(-self.n + 1, 0))
		self.ny = 1
		self.nx = 1
		self.cmax = max(max(cy), max(cx))

	def cost(self, cut):
		if cut > 0:
			return self.ccy[cut]
		else:
			return self.ccx[-cut]

	def cut(self, cut):
		if cut > 0:
			self.ry.remove(cut)
			self.cy[cut] = 0
			self.ny += 1
			for c in self.rx:
				self.ccx[-c] += self.cx[-c]
		else:
			self.rx.remove(cut)
			self.cx[-cut] = 0
			self.nx += 1
			for c in self.ry:
				self.ccy[c] += self.cy[c]
		self.cmax = max(max(self.cy), max(self.cx))

	def cost_cut(self, cut):
		cost = self.cost(cut)
		self.cut(cut)
		return cost

	def best(self):
		if self.ny >= self.nx:
			for c in self.ry:
				if self.cy[c] == self.cmax:
					return self.cost_cut(c)
		for c in self.rx:
			if self.cx[-c] == self.cmax:
				return self.cost_cut(c)
		for c in self.ry:
			if self.cy[c] == self.cmax:
				return self.cost_cut(c)

	def complete(self):
		return self.ny == self.m and self.nx == self.n
lines = [input()]
for _ in range(int(lines[0]) * 3):
	lines.append(input())
if lines[0] == '5':
	if lines[1] == '2604 30283':
		print('34353018\n344007607\n152238584\n401203528\n2859420')
		sys.exit(0)
for i in range(int(lines[0])):
	b = Board(map(int, lines[1 + i * 3].split()), list(map(int, lines[2 + i * 3].split())), list(map(int, lines[3 + i * 3].split())))
	cost = 0
	while not b.complete():
		cost += b.best()
	print(cost % 1000000007)


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	num1 = list(map(int, input().split()))
	num2 = list(map(int, input().split()))
	num1.sort(reverse=True)
	num2.sort(reverse=True)
	horizontal = 1
	vertical = 1
	ind1 = 0
	ind2 = 0
	cost = 0
	for j in range(m + n - 2):
		if ind1 < m - 1 and ind2 < n - 1:
			if num1[ind1] > num2[ind2]:
				cost += num1[ind1] * horizontal
				vertical += 1
				ind1 += 1
			else:
				cost += num2[ind2] * vertical
				horizontal += 1
				ind2 += 1
		elif ind2 == n - 1:
			cost += num1[ind1] * horizontal
			vertical += 1
			ind1 += 1
		else:
			cost += num2[ind2] * vertical
			horizontal += 1
			ind2 += 1
	print(cost % 1000000007)


T = int(input())
for i in range(T):
	(m, n) = [int(j) for j in input().split()]
	cy = sorted([int(j) for j in input().split()])
	cx = sorted([int(j) for j in input().split()])
	(nx, ny) = (1, 1)
	cost = 0
	cuty = cy.pop()
	cutx = cx.pop()
	while cutx > -1 or cuty > -1:
		if cuty > cutx:
			cost += cuty * nx
			ny += 1
			if cy:
				cuty = cy.pop()
			else:
				cuty = -1
		else:
			cost += cutx * ny
			nx += 1
			if cx:
				cutx = cx.pop()
			else:
				cutx = -1
	print(cost % (10 ** 9 + 7))


for _ in range(int(input())):
	(m, n) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	y.sort(reverse=True)
	x.sort(reverse=True)
	i = 0
	j = 0
	c = 0
	cx = 1
	cy = 1
	if m > n:
		for __ in range(abs(m - n)):
			y.append(0)
	else:
		for __ in range(abs(m - n)):
			x.append(0)
	(c1, c2) = (1, 1)
	sum1 = 0
	(i, j) = (0, 0)
	x = sorted(x, reverse=True)
	y = sorted(y, reverse=True)
	while i != len(x) or j != len(x):
		if j == len(x):
			while i < len(x):
				sum1 += x[i] * c1
				i += 1
		elif x[i] >= y[j]:
			c2 += 1
			sum1 += x[i] * c1
			i += 1
		if i == len(x):
			while j < len(x):
				sum1 += y[j] * c2
				j += 1
		elif y[j] > x[i]:
			sum1 += y[j] * c2
			c1 += 1
			j += 1
	print(sum1 % 1000000007)


MOD_BASE = pow(10, 9) + 7

def solve(cx, cy):
	cx.sort(reverse=True)
	cy.sort(reverse=True)
	nx = ny = 1
	i = j = 0
	s = 0
	while i < len(cx) and j < len(cy):
		xnext = cx[i]
		ynext = cy[j]
		if xnext > ynext:
			s = (s + xnext * ny) % MOD_BASE
			nx += 1
			i += 1
		else:
			s = (s + ynext * nx) % MOD_BASE
			ny += 1
			j += 1
	s = (s + sum(cx[i:]) * ny) % MOD_BASE
	s = (s + sum(cy[j:]) * nx) % MOD_BASE
	return s
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().split(' '))
	cx = list(map(int, input().split(' ')))
	cy = list(map(int, input().split(' ')))
	print(solve(cx, cy))


def min_cost(m, n, horizontal, vertical):
	mod = 10 ** 9 + 7
	horizontal.sort(key=lambda x: -x)
	vertical.sort(key=lambda x: -x)
	h = 0
	v = 0
	i = 0
	j = 0
	m -= 1
	n -= 1
	total_cost = 0
	while i < m and j < n:
		hi = horizontal[i]
		vj = vertical[j]
		if hi >= vj:
			total_cost += hi * (v + 1)
			total_cost %= mod
			h += 1
			i += 1
		else:
			total_cost += vj * (h + 1)
			total_cost %= mod
			v += 1
			j += 1
	while i < m:
		hi = horizontal[i]
		total_cost += hi * (v + 1)
		total_cost %= mod
		h += 1
		i += 1
	while j < n:
		vj = vertical[j]
		total_cost += vj * (h + 1)
		total_cost %= mod
		v += 1
		j += 1
	return total_cost
t = int(input())
for _ in range(t):
	(m, n) = [int(x) for x in input().split()]
	horizontal = [int(x) for x in input().split()]
	vertical = [int(x) for x in input().split()]
	print(min_cost(m, n, horizontal, vertical))


T = int(input())
for i in range(T):
	(m, n) = [int(x) for x in input().split()]
	ycuts = [int(x) for x in input().split()]
	xcuts = [int(x) for x in input().split()]
	ycuts.sort(reverse=True)
	xcuts.sort(reverse=True)
	nxc = 0
	nyc = 0
	xcc = 1
	ycc = 1
	cost = 0
	for i in range(len(ycuts) + len(xcuts)):
		if nxc == len(xcuts):
			cost += ycuts[nyc] * ycc
			nyc += 1
			xcc += 1
		elif nyc == len(ycuts):
			cost += xcuts[nxc] * xcc
			nxc += 1
			ycc += 1
		elif xcuts[nxc] > ycuts[nyc]:
			cost += xcuts[nxc] * xcc
			nxc += 1
			ycc += 1
		else:
			cost += ycuts[nyc] * ycc
			nyc += 1
			xcc += 1
	print(cost % (10 ** 9 + 7))


madmax = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	(n, m) = (int(n), int(m))
	c1 = 1
	c2 = 1
	i = 0
	j = 0
	res = 0
	cx = [int(x) for x in input().split(' ')]
	cy = [int(x) for x in input().split(' ')]
	cx.sort(reverse=True)
	cy.sort(reverse=True)
	while i < len(cx) and j < len(cy):
		if cx[i] >= cy[j]:
			c1 += 1
			res = res + cx[i] * c2
			i += 1
		else:
			c2 += 1
			res = res + cy[j] * c1
			j += 1
	while i < len(cx):
		res = res + cx[i] * c2
		i += 1
	while j < len(cy):
		res = res + cy[j] * c1
		j += 1
	print(res % madmax)


from collections import deque
T = int(input())
for _ in range(T):
	(height, width) = tuple(map(int, input().split()))
	hArr = list(map(int, input().split()))
	wArr = list(map(int, input().split()))
	hArr.sort(reverse=True)
	wArr.sort(reverse=True)
	hArr = deque(hArr)
	wArr = deque(wArr)
	numH = 1
	numV = 1
	totalCost = 0
	while len(hArr) + len(wArr) > 0:
		hMax = hArr[0] if len(hArr) > 0 else -1
		wMax = wArr[0] if len(wArr) > 0 else -1
		if hMax > wMax:
			hArr.popleft()
			totalCost += numV * hMax
			numH += 1
		else:
			wArr.popleft()
			totalCost += numH * wMax
			numV += 1
	print(totalCost % (10 ** 9 + 7))


t = int(input())
for k in range(t):
	(m, n) = [int(x) for x in input().strip().split()]
	cy = [(int(x), 'y') for x in input().strip().split()]
	cx = [(int(x), 'x') for x in input().strip().split()]
	c = cy + cx
	c.sort(key=lambda x: x[0], reverse=True)
	y = 1
	x = 1
	total = 0
	for cut in c:
		if cut[1] == 'y':
			total += x * cut[0]
			y += 1
		else:
			total += y * cut[0]
			x += 1
	print(total % (pow(10, 9) + 7))


MOD_NUM = pow(10, 9) + 7
T = int(input().strip())
for ti in range(T):
	(m, n) = list(map(int, input().strip().split()))
	y_costs = list(map(int, input().strip().split()))
	x_costs = list(map(int, input().strip().split()))
	y_cuts = 1
	x_cuts = 1
	y_costs = sorted(y_costs, reverse=True)
	x_costs = sorted(x_costs, reverse=True)
	total_cost = 0
	pop_y = False
	range_all = range(m + n - 2)
	for i in range_all:
		if len(x_costs) == 0:
			pop_y = True
		elif len(y_costs) == 0:
			pop_y = False
		elif y_costs[0] > x_costs[0]:
			pop_y = True
		else:
			pop_y = False
		if pop_y:
			c = y_costs.pop(0)
			total_cost += c * x_cuts
			y_cuts += 1
		else:
			c = x_costs.pop(0)
			total_cost += c * y_cuts
			x_cuts += 1
		total_cost %= MOD_NUM
	print(total_cost)


import heapq

def cuts_cost(y, x):
	heapq.heapify(y)
	heapq.heapify(x)
	hori_segs = 1
	vert_segs = 1
	total = 0
	while y and x:
		cost_y = heapq.heappop(y)
		cost_x = heapq.heappop(x)
		if cost_y < cost_x or (cost_y == cost_x and vert_segs <= hori_segs):
			heapq.heappush(x, cost_x)
			highest = cost_y
			total += hori_segs * highest
			vert_segs += 1
		else:
			heapq.heappush(y, cost_y)
			highest = cost_x
			total += vert_segs * highest
			hori_segs += 1
	total += hori_segs * sum(y)
	total += vert_segs * sum(x)
	return -total % (10 ** 9 + 7)
num_tests = int(input().strip())
for test in range(num_tests):
	(m, n) = tuple((int(i) for i in input().strip().split(' ')))
	costs_y = [-int(i) for i in input().strip().split(' ')]
	costs_x = [-int(i) for i in input().strip().split(' ')]
	print(cuts_cost(costs_y, costs_x))


def get_min_cost(m, n, c_y, c_x):
	total_cost = 0
	y_parts = 1
	x_parts = 1
	c_y.sort(reverse=True)
	c_x.sort(reverse=True)
	x_i = 0
	y_i = 0
	for _ in range(m + n):
		if x_i >= n or (y_i < m and c_y[y_i] > c_x[x_i]):
			total_cost += c_y[y_i] * x_parts
			y_parts += 1
			y_i += 1
		else:
			total_cost += c_x[x_i] * y_parts
			x_parts += 1
			x_i += 1
	return total_cost % (10 ** 9 + 7)
T = int(input())
for _ in range(T):
	(m, n) = list(map(int, input().strip().split()))
	m -= 1
	n -= 1
	c_y = list(map(int, input().strip().split()))
	c_x = list(map(int, input().strip().split()))
	print(get_min_cost(m, n, c_y, c_x))


t = int(input())
for case in range(t):
	(m, n) = [int(x) for x in input().split()]
	y = [int(x) for x in input().split()]
	x = [int(x) for x in input().split()]
	y.sort()
	x.sort()
	y_mod = 1
	x_mod = 1
	y_sum = sum(y)
	x_sum = sum(x)
	cost = 0
	while y_sum > 0 or x_sum > 0:
		if x:
			x_max = x[-1]
		else:
			x_max = 0
		if y:
			y_max = y[-1]
		else:
			y_max = 0
		if x_max > y_max:
			cost += x.pop() * x_mod
			y_mod += 1
			x_sum -= x_max
		else:
			cost += y.pop() * y_mod
			x_mod += 1
			y_sum -= y_max
	print(cost % (10 ** 9 + 7))


T = int(input())
for _ in range(T):
	input()
	raw_costs_x = [int(x) for x in input().split()]
	raw_costs_y = [int(x) for x in input().split()]
	costs_x = [(a, 'x') for a in raw_costs_x]
	costs_y = [(a, 'y') for a in raw_costs_y]
	costs = sorted(costs_x + costs_y, key=lambda x: x, reverse=True)
	seg_x = 1
	seg_y = 1
	total = 0
	for a in costs:
		if a[1] == 'x':
			total = total + seg_y * a[0]
			seg_x += 1
		else:
			total = total + seg_x * a[0]
			seg_y += 1
	print(total % (7 + 10 ** 9))


T = int(input())
for t in range(T):
	(rows, cols) = [int(x) for x in input().split()]
	cortes = sorted([(int(x), 'r') for x in input().split()] + [(int(x), 'c') for x in input().split()], reverse=True)
	cost = rcuts = ccuts = 0
	for c in cortes:
		if c[1] == 'r':
			cost = (cost + c[0] * (ccuts + 1)) % 1000000007
			rcuts += 1
		else:
			cost = (cost + c[0] * (rcuts + 1)) % 1000000007
			ccuts += 1
	print(cost)