Problem:
 Score : 500 points    Problem Statement On an xy plane, in an area satisfying 0 ≤ x ≤ W, 0 ≤ y ≤ H , there is one house at each and every point where both x and y are integers.  There are unpaved roads between every pair of points for which either the x coordinates are equal and the difference between the y coordinates is 1 , or the y coordinates are equal and the difference between the x coordinates is 1 .  The cost of paving a road between houses on coordinates (i,j) and (i+1,j) is p_i for any value of j , while the cost of paving a road between houses on coordinates (i,j) and (i,j+1) is q_j for any value of i .  Mr. Takahashi wants to pave some of these roads and be able to travel between any two houses on paved roads only. Find the solution with the minimum total cost.      Constraints  1 ≦ W,H ≦ 10^5  1 ≦ p_i ≦ 10^8(0 ≦ i ≦ W-1)  1 ≦ q_j ≦ 10^8(0 ≦ j ≦ H-1)  p_i (0 ≦ i ≦ W−1) is an integer.  q_j (0 ≦ j ≦ H−1) is an integer.         Input Inputs are provided from Standard Input in the following form.  W  H  p_0 : p_{W-1}  q_0 : q_{H-1}       Output Output an integer representing the minimum total cost.        Sample Input 1 2 2
3
5
2
7      Sample Output 1 29  It is enough to pave the following eight roads.   Road connecting houses at (0,0) and (0,1)  Road connecting houses at (0,1) and (1,1)  Road connecting houses at (0,2) and (1,2)  Road connecting houses at (1,0) and (1,1)  Road connecting houses at (1,0) and (2,0)  Road connecting houses at (1,1) and (1,2)  Road connecting houses at (1,2) and (2,2)  Road connecting houses at (2,0) and (2,1)        Sample Input 2 4 3
2
4
8
1
2
9
3      Sample Output 2 60

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    W,H = LI()
    s = []
    for _ in range(W):
        s.append((NI(),0))
    for _ in range(H):
        s.append((NI(),1))
    s.sort()
    x = 0
    y = 0
    ans = 0
    for r,d in s:
        if d == 0:
            ans += (H - y + 1) * r
            x += 1
        else:
            ans += (W - x + 1) * r
            y += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):











w, h = list(map(int, input().split()))

yoko = [(int(input()), 'yoko') for _ in range(w)]
tate = [(int(input()), 'tate') for _ in range(h)]

sorted_edge = sorted(yoko + tate, key=lambda x: x[0])

ans = 0
tate_num = 0
yoko_num = 0
for length, direction in sorted_edge:
    if direction == 'tate':
        ans += length * (w + 1 - yoko_num)
        tate_num += 1
    else:
        ans += length * (h + 1 - tate_num)
        yoko_num += 1

print(ans)

Solution (Python):
W,H = map(int,input().split())
edges = []
for i in range(W):
    p = int(input())
    edges.append((p,0))
for i in range(H):
    q = int(input())
    edges.append((q,1))
edges.sort(key = lambda x:x[0])
ans = 0
w = W+1
h = H+1
for a,b in edges:
    if b == 0:
        w -= 1
        ans += h*a
    else:
        h -= 1
        ans += w*a
print(ans)

Solution (Python):
import sys
import io, os
input = sys.stdin.buffer.readline


w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]

E = []
for p in P:
    E.append((p, 0))
for q in Q:
    E.append((q, 1))
E.sort(reverse=True)

a = w+1
b = h+1
ans = 0
while a >1 or b > 1:
    c, t = E.pop()
    if t == 0:
        ans += c*b
        a -= 1
    else:
        ans += c*a
        b -= 1
print(ans)

Solution (Python):
import sys
import io, os
input = sys.stdin.buffer.readline


w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]

E = []
for p in P:
    E.append((p, 0))
for q in Q:
    E.append((q, 1))
E.sort(reverse=True)

a = w+1
b = h+1
ans = 0
while a >1 or b > 1:
    c, t = E.pop()
    if t == 0:
        ans += c*b
        a -= 1
    else:
        ans += c*a
        b -= 1
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
w, h = map(int, input().split())
p = sorted(int(input()) for _ in range(w))
q = sorted(int(input()) for _ in range(h))



ans = sum(p) + sum(q)
for i in range(w):
    num = h - bisect_left(q, p[i])
    ans += num * p[i]
for i in range(h):
    num = w - bisect_right(p, q[i])
    ans += num * q[i]
print(ans)

Solution (Python):

import sys
def main(W, H, P, Q):
    E = [(0, p) for p in P] + [(1, q) for q in Q]
    E.sort(key=lambda x: x[1])
    cost = 0
    R = [H + 1, W + 1]
    for d, c in E:
        cost += c * R[d]
        R[d ^ 1] -= 1
    print(cost)

if __name__ == '__main__':
    input = sys.stdin.readline
    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    Q = [int(input()) for _ in range(H)]
    main(W, H, P, Q)

Solution (Python):
w, h = list(map(int, input().split()))
xs = [int(input()) for _ in range(w)]
ys = [int(input()) for _ in range(h)]

x_cnt = w + 1
y_cnt = h + 1

i = 0
j = 0
xs.sort()
ys.sort()

ans = 0
while i < len(xs) or j < len(ys):
    if i >= len(xs) or (j < len(ys) and ys[j] < xs[i]):
        ans += x_cnt * ys[j]
        j += 1
        y_cnt -= 1
    else:
        ans += y_cnt * xs[i]
        i += 1
        x_cnt -= 1
print(ans)

Solution (Python):
w, h = map(int, input().split())
p = [int(input()) for _ in range(w)]
q = [int(input()) for _ in range(h)]
ans = sum(p) + sum(q)
p.sort(reverse = True)
q.sort(reverse = True)
i = 0
for j in range(w):
    while True:
        if i == h:
            break
        if p[j] >= q[i]:
            break
        i += 1
    ans += i * p[j]
i = 0
for j in range(h):
    while True:
        if i == w:
            break
        if q[j] > p[i]:
            break
        i += 1
    ans += i * q[j]
print(ans)

Solution (Python):
n,m=map(int,input().split())
p=[[int(input()),0]for _ in range(n)]
q=[[int(input()),1]for _ in range(m)]
a=p+q
a.sort()
pp=n+1
qq=m+1
ans=0
for x,f in a:
  if f==0:
    ans+=x*qq
    pp=max(0,pp-1)
  else:
    ans+=x*pp
    qq=max(0,qq-1)
print(ans)

Solution (Python):
from heapq import heapify, heappop, heappush
W,H = map(int,input().split())
R = []
for i in range(W):
  temp = int(input())
  heappush(R,(temp,"x"))
for i in range(H):
  temp = int(input())
  heappush(R,(temp,"y"))
X = 0
Y = 0
ans = 0

for i in range(H+W):
  cost,muki = heappop(R)
  
  if muki == "x":
    ans += cost*(H+1-Y)
    
    X += 1
  else:
    ans += cost*(W+1-X)
    
    Y += 1
print(ans)

Solution (Python):
w, h = map(int, input().split())
plst = [int(input()) for _ in range(w)]
qlst = [int(input()) for _ in range(h)]
plst.sort()
qlst.sort()
p_cnt = w + 1
q_cnt = h + 1
ppos = 0
qpos = 0
ans = 0
while 1:
    if plst[ppos] < qlst[qpos]:
        ans += plst[ppos] * q_cnt
        p_cnt -= 1
        ppos += 1
        if ppos == w:
            ans += sum(qlst[qpos:])
            break
    else:
        ans += qlst[qpos] * p_cnt
        q_cnt -= 1
        qpos += 1
        if qpos == h:
            ans += sum(plst[ppos:])
            break
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


w,h = list(map(int, input().split()))
p = [None]*(w+h)
for i in range(w):
    p[i] = (int(input()), 0)
for j in range(h):
    p[w+j] = (int(input()), 1)
p.sort()
nums = [h+1,w+1]
ans = 0
i = 0
es = 0
while es<(h+1)*(w+1)-1:
    v, d = p[i]
    if nums[d]==0:
        pass
    else:
        ans += v * nums[d]
        es += nums[d]
        nums[int(not d)] -= 1
    i += 1

print(ans)

Solution (Python):
W,H=map(int,input().split())
P=[int(input()) for i in range(W)]
Q=[int(input()) for i in range(H)]
R=[]
for i in range(W):
  R.append((P[i],0))
for i in range(H):
  R.append((Q[i],1))
P=0
R.sort()
H,W=H+1,W+1
for i in range(len(R)):
  if R[i][1]:
    P+=W*R[i][0]
    H-=1
  else:
    P+=H*R[i][0]
    W-=1
print(P)

Solution (Python):
w,h=map(int,input().split())
p=[int(input()) for _ in range(w)]
q=[int(input()) for _ in range(h)]
p.sort(reverse=True)
q.sort(reverse=True)
ans=0
c,r=w+1,h+1
while p or q:
  if q and (not p or p[-1]>q[-1]):
    ans+=q.pop()*c
    r-=1
  else:
    ans+=p.pop()*r
    c-=1
print(ans)

Solution (Python):
W,H = map(int, input().split())
P = [0] * W
Q = [0] * H
for i in range(W):
  P[i] = int(input())
for i in range(H):
  Q[i] = int(input())
  
P.sort()
Q.sort()


infv = int(1e9)
P.append(infv)
Q.append(infv)

cumP = [0] * (W+1)
cumQ = [0] * (H+1)
for i in range(W):
  cumP[i+1] = cumP[i] + P[i]
for i in range(H):
  cumQ[i+1] = cumQ[i] + Q[i]
  


y,x = 0,0
cost = 0
while y <= H and x <= W:
  
  
  if x == W and y == H:
    break
  elif P[x] <= Q[y]:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  else:
    cost += Q[y]
    y += 1
    cost += cumP[x]
    
print(cost)

Solution (Python):
W,H = map(int, input().split())
P = [0] * W
Q = [0] * H
for i in range(W):
  P[i] = int(input())
for i in range(H):
  Q[i] = int(input())
  
P.sort()
Q.sort()
cumP = [0] * (W+1)
cumQ = [0] * (H+1)
for i in range(W):
  cumP[i+1] = cumP[i] + P[i]
for i in range(H):
  cumQ[i+1] = cumQ[i] + Q[i]
  


y,x = 0,0
cost = 0
while y <= H and x <= W:
  
  
  if x == W and y == H:
    break
  elif x == W:
    cost += Q[y]
    y += 1
    cost += cumP[x]    
  elif y == H:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  elif P[x] <= Q[y]:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  else:
    cost += Q[y]
    y += 1
    cost += cumP[x]
    
print(cost)

Solution (Python):
W,H = map(int, input().split())
P = [0] * W
Q = [0] * H
for i in range(W):
  P[i] = int(input())
for i in range(H):
  Q[i] = int(input())
  
P.sort()
Q.sort()
cumP = [0] * (W+1)
cumQ = [0] * (H+1)
for i in range(W):
  cumP[i+1] = cumP[i] + P[i]
for i in range(H):
  cumQ[i+1] = cumQ[i] + Q[i]
  


y,x = 0,0
cost = 0
while y <= H and x <= W:
  
  
  if x == W and y == H:
    break
  elif x == W:
    cost += Q[y]
    y += 1
    cost += cumP[x]    
  elif y == H:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  elif P[x] <= Q[y]:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  else:
    cost += Q[y]
    y += 1
    cost += cumP[x]
    
print(cost)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq


w,h =readints()
p = [readint() for i in range(w)]
q = [readint() for i in range(h)]

heapq.heapify(p)
heapq.heapify(q)

edge = 0
cost = 0
used = [0,0]

while edge < (h+1)*(w+1)-1:
    if p and q:
        if p[0]<q[0]:
            flag = 1
        else:
            flag = 0
    elif p:
        flag = 1
    else:
        flag = 0
    if flag:
        x = heapq.heappop(p)
        edge += h+1-used[1]
        cost += x * (h+1-used[1])
        used[0] += 1
    else:
        x = heapq.heappop(q)
        edge += w+1-used[0]
        cost += x * (w+1-used[0])
        used[1] += 1

print(cost)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

w,h = inm()
p = []
q = []
for i in range(w):
    p.append(inn())
for i in range(h):
    q.append(inn())
x = w+1
y = h+1
p.sort(reverse=True)
q.sort(reverse=True)
ans = 0
while x>1 or y>1:
    
    if x>1 and (y==1 or p[-1]<=q[-1]):
        ans += p[-1]*y
        p.pop()
        x -= 1
    else:
        ans += q[-1]*x
        q.pop()
        y -= 1
print(ans)

Solution (Python):
import bisect
w, h = map(int, input().split())
p = [int(input()) for _ in range(w)]
q = [int(input()) for _ in range(h)]

q.sort()
q_cum = [0 for _ in range(h+1)]
for i in range(h):
    q_cum[i+1] = q_cum[i] + q[i]

ans = sum(q)
for i in range(w):
    x = bisect.bisect_left(q, p[i])
    ans += q_cum[x] + p[i] * (h + 1 - x)

print(ans)

Solution (Python):
import sys
import numpy as np
input = sys.stdin.buffer.readline

W, H = map(int, input().split())
ps = sorted(int(input()) for _ in range(W))
qs = sorted(int(input()) for _ in range(H))


q_cumsum = np.cumsum([0] + qs)

ans = sum(ps) + q_cumsum[-1]

index = 0
for p in ps:
    while index < H and qs[index] <= p:
        index += 1
    ans += q_cumsum[index] + p * (H - index)
    
print(ans)

Solution (Python):


W, H = map(int, input().split())
d = []
for i in range(W):
    x = int(input())
    d.append((x, 0))

for j in range(H):
    y = int(input())
    d.append((y, 1))
d.sort()
X = H+1
Y = W+1

ans = 0

for que in d:
    weight, pos = que
    if pos <1:
        ans += X*weight
        Y -= 1
    else:
        ans += Y*weight
        X -= 1
print(ans)

Solution (Python):


W, H = map(int, input().split())
d = []
for i in range(W):
    x = int(input())
    d.append((x, 0))

for j in range(H):
    y = int(input())
    d.append((y, 1))
d.sort()
X = H+1
Y = W+1

ans = 0

for que in d:
    weight, pos = que
    if pos <1:
        ans += X*weight
        Y -= 1
    else:
        ans += Y*weight
        X -= 1
print(ans)

Solution (Python):


W, H = map(int, input().split())
d = []
for i in range(W):
    x = int(input())
    d.append((x, "x"))

for j in range(H):
    y = int(input())
    d.append((y, "y"))
d.sort()
X = H+1
Y = W+1

ans = 0

for que in d:
    weight, pos = que
    if pos == "x":
        ans += X*weight
        Y -= 1
    else:
        ans += Y*weight
        X -= 1
print(ans)

Solution (Python):
W,H,*L = map(int, open(0).read().split())
ls = [0]*(W+H)
for i,c in enumerate(L):
  if i<W:
    ls[i] = (c,0)
  else:
    ls[i] = (c,1)
ls.sort()
P = 0
Q = 0
cnt = (W+1)*(H+1)-1
ans = 0
for c,s in ls:
  if s:
    m = min(cnt,W+1-P)
    cnt -= m
    ans += m*c
    Q += 1
  else:
    m = min(cnt,H+1-Q)
    cnt -= m
    ans += m*c
    P += 1
  if cnt==0:
    print(ans)
    break

Solution (Python):
import sys
input = sys.stdin.readline

W, H = map(int, input().split())
p = [int(input()) for i in range(W)]
q = [int(input()) for i in range(H)]
p.sort()
q.sort()
row = H + 1
col = W + 1
i = j = 0
ans = 0
while row > 1 or col > 1:
    if i < W and (j == H or p[i] < q[j]):
        ans += p[i] * row
        col -= 1
        i += 1
    else:
        ans += q[j] * col
        row -= 1
        j += 1
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



W,H = LI()
p = LIR(W,1)
q = LIR(H,1)

p.sort()
cusum = [p[0]]
for i in range(1,W):
    cusum.append(cusum[-1]+p[i])
ans = cusum[-1]

for i in range(H):
    place = bisect_left(p,q[i])
    temp = cusum[place-1] if place >= 1 else 0
    ans += temp + q[i]*(W+1-place)

print(ans)

Solution (Python):
w,h= map(int,input().split())
p = sorted([int(input()) for _ in range(w)],reverse=True)
q = sorted([int(input()) for _ in range(h)],reverse=True)
sumrp = [0]*w
sumrp[-1]=p[-1]
for i in range(w-2,-1,-1):sumrp[i]=sumrp[i+1]+p[i]
sumrq = [0]*h
sumrq[-1]=q[-1]
for i in range(h-2,-1,-1):sumrq[i]=sumrq[i+1]+q[i]
gen=0
pid = qid = 0
w+=1
h+=1
while True:
    if pid==w-1:
        gen+=sumrq[qid]
        break
    if qid==h-1:
        gen+=sumrp[pid]
        break
    if p[pid]>=q[qid]:
        gen+=p[pid]
        gen+=sumrq[qid]
        pid+=1
    elif p[pid]<q[qid]:
        gen+=q[qid]
        gen+=sumrp[pid]
        qid+=1
print(gen)

Solution (Python):
import heapq

W, H = map(int, input().split(" "))
que = []
for _ in range(W):
    heapq.heappush(que, (int(input()), 'W'))

for _ in range(H):
    heapq.heappush(que, (int(input()), 'H'))

W += 1
H += 1
ans = 0
while que:
    cost, pos = heapq.heappop(que)
    if pos == 'W':
        ans += cost * H
        W -= 1
    else:
        ans += cost * W
        H -= 1

print(ans)

Solution (Python):

w,h = list(map(int, input().split()))
ws = []
hs = []
for i in range(w): ws.append(int(input()))
for i in range(h): hs.append(int(input()))

ws.sort(reverse = True)
hs.sort(reverse = True)

remainW = w
remainH = h
aliveW = [1 for i in range(w)]
aliveH = [1 for i in range(h)]

ans = 0
while(remainW>0 or remainH>0):
    
    costW = ws[remainW-1] * (remainH + 1)
    costH = hs[remainH-1] * (remainW + 1)
    if(remainH!=0 and (ws[remainW-1] > hs[remainH-1] or remainW==0)):
        ans += costH
        remainH = max(0,remainH-1)
    else:
        ans += costW
        remainW = max(0,remainW-1)
print(ans)

Solution (Python):
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline

W, H, *pq = map(int, read().split())
pq = list(zip(pq[:W], ['p'] * W)) + list(zip(pq[W:], ['q'] * H))
pq.sort(key=itemgetter(0))
answer = 0
x = W + 1
y = H + 1
for cost, i in pq:
    if i == 'p':
        answer += cost * y
        x -= 1
    else:
        answer += cost * x
        y -= 1

print(answer)

Solution (Python):
W, H = map(int, input().split())
PQ = [[int(input()), 'x'] for w in range(W)]
PQ += [[int(input()), 'y'] for h in range(H)]
PQ.sort()

_W = W + 1; _H = H + 1
ans = 0
for v, z in PQ:
  if z == 'x':
    if _W > 1:
      ans += _H * v
      _W -= 1
  else: 
    if _H > 1:
      ans += _W * v
      _H -= 1
  
  if _W == _H == 1:
    break

print(ans)

Solution (Python):
import itertools
import bisect

W, H = map(int, input().split())
P = [int(input()) for w in range(W)]
Q = [int(input()) for h in range(H)]

P.sort()
accum_P = list(itertools.accumulate(P))
ans = accum_P[-1]
for q in Q:
  idx = bisect.bisect_left(P, q)
  if idx >= W + 1:
    ans += accum_P[W-1] + q
  elif idx == 0:
    ans += (W + 1) * q
  else:
    ans += accum_P[idx-1] + (W + 1 - idx)*q

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

W, H = map(int,input().split())

P = [int(input()) for _ in range(W)]
Q = [int(input()) for _ in range(H)]

P.sort()
Q.sort()

res = 0

for i in range(W):
    res += (H + 1 - bisect_left(Q, P[i])) * P[i]

for i in range(H):
    res += (W + 1 - bisect_right(P, Q[i])) * Q[i]
    
print(res)

Solution (Python):
import sys

w, h, *pq = map(int, sys.stdin.buffer.read().split())
vertical_split = 0
horizontal_split = 0
costs = []
costs.extend((p, 0) for p in pq[:w])
costs.extend((q, 1) for q in pq[w:])
costs.sort(reverse=True)

ans = 0
for c, t in costs:
    if t == 0:
        ans += c * (horizontal_split + 1)
        vertical_split += 1
    else:
        ans += c * (vertical_split + 1)
        horizontal_split += 1
print(ans)

Solution (Python):
W, H, *L = map(int, open(0).read().split())
p = L[:W]
q = L[W:]
H += 1
W += 1
h = 0
w = 0
ls = [(c,0) for c in p]+[(c,1) for c in q]
ls.sort()
ans = 0
for c,s in ls:
  if s==1:
    ans += c*(W-w)
    h += 1
  if s==0:
    ans += c*(H-h)
    w += 1
print(ans)

Solution (Python):
w,h=map(int, input().split())
a=[int(input())for i in range(w)]
b=[int(input())for i in range(h)]
from heapq import heappop,heappush
q=[]
w+=1
h+=1
for i in a:
  heappush(q,(i,0))
for i in b:
  heappush(q,(i,1))
ans=0
while q:
  c,t=heappop(q)
  if t==0:
    ans+=h*c
    w-=1
  else:
    ans+=w*c
    h-=1
print(ans)

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    w, h = map(int, input().split())
    pq = [None] * (w + h)

    
    
    
    
    for i in range(w + h):
        if i < w:
            pq[i] = (int(input()), 'x')
        else:
            pq[i] = (int(input()), 'y')

    x_count = w + 1
    y_count = h + 1
    ans = 0

    
    
    
    
    for cost, flag in sorted(pq):
        if flag == 'x':
            ans += cost * y_count
            x_count -= 1
        else:
            ans += cost * x_count
            y_count -= 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    w, h = map(int, input().split())
    pq = [None] * (w + h)

    for i in range(w + h):
        if i < w:
            pq[i] = (int(input()), 'x')
        else:
            pq[i] = (int(input()), 'y')

    x_count = w + 1
    y_count = h + 1
    ans = 0

    for cost, flag in sorted(pq):
        if flag == 'x':
            ans += cost * y_count
            x_count -= 1
        else:
            ans += cost * x_count
            y_count -= 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left, bisect_right

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

W, H = lr()
P = [ir() for _ in range(W)]
Q = [ir() for _ in range(H)]
P.sort()
Q.sort()
answer = 0
for p in P:
    i = bisect_left(Q, p)
    answer += (H - i + 1) * p

for q in Q:
    i = bisect_right(P, q)
    answer += (W - i + 1) * q

print(answer)

Solution (Python):
w, h = [int(i) for i in input().split()]
p = [(int(input()),0) for _ in range(w)]
q = [(int(input()),1) for _ in range(h)]
pq = sorted(p + q)
hh = 0
ww = 0
ans = 0
for i in pq:
    if i[1] == 0:
        ans += i[0] * (h+1 - hh)
        ww += 1
    else:
        ans += i[0] * (w+1- ww)
        hh += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
w,h = map(int,input().split())
a = [10**18]+[int(input()) for i in range(w)]
b = [10**18]+[int(input()) for i in range(h)]
a.sort(reverse=True)
b.sort(reverse=True)
ans = 0
while len(a)>1 or len(b)>1:
  if a[-1]<b[-1]:
    ans += a[-1]*len(b)
    a.pop()
  else:
    ans += b[-1]*len(a)
    b.pop()
print(ans)

Solution (Python):
w,h = map(int,input().split())
a = [10**18]+[int(input()) for i in range(w)]
b = [10**18]+[int(input()) for i in range(h)]
a.sort(reverse=True)
b.sort(reverse=True)
ans = 0
while len(a)>1 or len(b)>1:
  if a[-1]<b[-1]:
    ans += a[-1]*len(b)
    a.pop()
  else:
    ans += b[-1]*len(a)
    b.pop()
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    W,H = map(int,input().split())
    l = []
    for _ in range(W):
        p = int(input())
        l.append((p,0))
    for _ in range(H):
        p = int(input())
        l.append((p,1))
        
    l.sort(key=itemgetter(0))
    a,b = W+1,H+1
    ans = 0
    for d,now in l:
        if now == 0:
            ans += d*b
            a -= 1
        else:
            ans += d*a
            b -= 1
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

W, H = map(int, input().split())

inf = 10**10
yoko = [inf]
tate = [inf]

for _ in range(W):
    p = int(input())
    heapq.heappush(yoko, p)
for _ in range(H):
    p = int(input())
    heapq.heappush(tate, p)



ans = 0
while H > 0 or W > 0:
    if yoko[0] < tate[0]:
        ans += (H+1) * heapq.heappop(yoko)
        W -= 1
    else:
        ans += (W+1) * heapq.heappop(tate)
        H -= 1

print(ans)

Solution (Python):
def main():
	w, h, *L = map(int, open(0).read().split())
	x, y, ans = w, h, 0
	for c in sorted(L[:w] + [-q for q in L[w:]], key=abs):
		if c > 0:
			if x:
				ans += c * (y + 1)
				x -= 1
		else:
			if y:
				ans -= c * (x + 1)
				y -= 1
		if x == y == 0:
			break
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
w,h,*L=map(int,open(0).read().split())
P=L[:w];Q=[-qj for qj in L[w:]]
x,y,ans=w,h,0
for c in sorted(P+Q,key=abs):
	if c>0:
		if x:ans+=c*(y+1);x-=1
	else:
		if y:ans-=c*(x+1);y-=1
print(ans)

Solution (Python):
w,h,*L=map(int,open(0).read().split())
P=L[:w];Q=L[w:]
x,y=w,h
sss=[]
for i,pi in enumerate(P):
	sss.append((pi,1))
for j,qj in enumerate(Q):
	sss.append((qj,0))
sss.sort()
ans=0
for c,f in sss:
	if f and x:
		x-=1
		ans+=c*(y+1)
	elif not f and y:
		y-=1
		ans+=c*(x+1)
print(ans)

Solution (Python):
def main():
    W,H=map(int, input().split())
    P=sorted(int(input())for _ in range(W))
    Q=sorted(int(input())for _ in range(H))
    i,j,ans=0,0,0
    while i<W and j<H:
        if P[i]<Q[j]:
            ans+=P[i]*(H-j+1)
            i+=1
        else:
            ans+=Q[j]*(W-i+1)
            j+=1
    while i<W:
        ans+=P[i]*(H-j+1)
        i+=1
    while j<H:
        ans+=Q[j]*(W-i+1)
        j+=1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]
heapq.heapify(P)
heapq.heapify(Q)
ans = 0
count_x, count_y = 0, 0
while P or Q:
  if not P:
    temp = heapq.heappop(Q)
    ans += temp * (w+1-count_x)
    count_y += 1
  elif not Q:
    temp = heapq.heappop(P)
    ans += temp * (h+1-count_y)
    count_x += 1
  else:
    tp, tq = P[0], Q[0]
    if tp < tq:
      temp = heapq.heappop(P)
      ans += temp * (h+1-count_y)
      count_x += 1
    else:
      temp = heapq.heappop(Q)
      ans += temp * (w+1-count_x)
      count_y += 1
print(ans)

Solution (Python):
W, H = map(int, input().split())
p = [int(input()) for _ in range(W)]
q = [int(input()) for _ in range(H)]
edges = []
for i in range(W):
    edges.append((p[i], 0))
for i in range(H):
    edges.append((q[i], 1))
edges.sort()
cnt_h = 0
cnt_w = 0
res = 0
for c, d in edges:
    if d == 0:
        cnt_w+=1
        res+=(H+1-cnt_h)*c
    else:
        cnt_h+=1
        res+=(W+1-cnt_w)*c
print(res)

Solution (Python):
w,h=map(int, input().split())
p=[int(input()) for i in range(w)]
q=[int(input()) for i in range(h)]
p.append(0)
q.append(0)
p.sort()
p.reverse()
q.sort()
q.reverse()

count=w*h
row=0
line=0
i=0
j=0
ans=0

while count>0:
    if p[i]>=q[j]:
        ans+=p[i]*(h-line)

        count-=h-line
        i+=1
        row+=1

    else:
        ans+=q[j]*(w-row)

        count-=w-row
        j+=1
        line+=1
x=sum(p)*(h+1)+sum(q)*(w+1)
print(x-ans)

Solution (Python):
import sys
input = sys.stdin.readline
w, h = map(int,input().split())
P = [int(input()) for i in range(w)]
Q = [int(input()) for i in range(h)]
R = [P, Q]

nn = [w+1, h+1]
A = []
for i in range(w):
    A.append([P[i], i, 0])
for i in range(h):
    A.append([Q[i], i, 1])

A.sort()
ans = 0
for i in range(len(A)):
    d = A[i][0]
    j = A[i][1]
    t = A[i][2]
    ans += d * nn[(t+1)%2]
    
    nn[t] = max(1, nn[t]-1)
    if nn == [1, 1]:
        break
print(ans)

Solution (Python):
def examA():
    S = SI(); N = len(S)
    T = "CODEFESTIVAL2016"
    ans = 0
    for i in range(N):
        if S[i]!=T[i]:
            ans +=1
    print(ans)
    return

def examB():
    N, A, B = LI()
    S = SI()
    d = defaultdict(int)
    for s in S:
        if s=="a":
            if d["a"]+d["b"]<A+B:
                print("Yes")
                d[s] += 1
            else:
                print("No")
        elif s=="b":
            if d["a"]+d["b"]<A+B and d["b"]<B:
                print("Yes")
                d[s] += 1
            else:
                print("No")
        else:
            print("No")
    return

def examC():
    W, H = LI()
    P = [I() for _ in range(W)]; P.sort()
    Q = [I() for _ in range(H)]; Q.sort()
    dh = 0; dw = 0
    p = 0; q = 0
    ans = 0
    for i in range(H+W):
        if (q<H and p<W and P[p]<Q[q]) or not q<H:
            ans += P[p]*(H+1-dh)
            p +=1; dw +=1
        else:
            ans += Q[q]*(W+1-dw)
            q +=1; dh+=1
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET, _ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 1e-9
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

Solution (Python):

W,H = map(int,input().split())

t = H+1
y = W+1

ans = 0

lis = []

for i in range(W):
    p = int(input())
    lis.append([p,"y",i])

for i in range(H):
    q = int(input())
    lis.append([q,"t",i])

lis.sort()

for i in lis:

    ncost = i[0]
    ndir = i[1]
    

    if ndir == "t":
        t -= 1
        ans += ncost * max(0 , y)

    else:
        y -= 1
        ans += ncost * max(0 , t)

print (ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_right

    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    P.sort()
    P_count = [0] * (W + 2)

    Q = [int(input()) for _ in range(H)]
    Q.sort()

    ans = 0
    for q in Q:
        tmp = bisect_right(P, q)
        P_count[tmp] += 1
        ans += q * (1 + W - tmp)

    for i in range(W, - 1, -1):
        P_count[i] += P_count[i + 1]

    for index, p in enumerate(P):
        ans += p * (P_count[index + 1] + 1)

    print (ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right


    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    P.sort()
    P_count = [0] * (W + 2)

    Q = [int(input()) for _ in range(H)]
    Q.sort()

    ans = 0
    for q in Q:
        tmp = bisect_right(P, q)
        P_count[tmp] += 1
        ans += q * (1 + W - tmp)

    for i in range(W, - 1, -1):
        P_count[i] += P_count[i + 1]
    
    
    
    
    for index, p in enumerate(P):
        ans += p * (P_count[index + 1] + 1)
    print (ans)
    
    

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right


    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    P.sort()

    Q = [int(input()) for _ in range(H)]
    Q.sort()

    ans = 0
    for q in Q:
        tmp = bisect_right(P, q)
        
        ans += q * (1 + W - tmp)
        

    for p in P:
        tmp = bisect_left(Q, p)
        ans += p * (1 + H - tmp)

    print (ans)
    
    

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


W, H = map(int, input().split())
P = [int(input()) for _ in range(W)]
P.sort()

Q = [int(input()) for _ in range(H)]
Q.sort()

ans = 0
for q in Q:
    tmp = bisect_right(P, q)
    
    ans += q * (1 + W - tmp)
    

for p in P:
    tmp = bisect_left(Q, p)
    ans += p * (1 + H - tmp)

print (ans)