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 bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(W, H, P, Q):
    ans = sum(P) + sum(Q)

    P.sort()
    Q.sort()
    for q in Q:
        i = bisect.bisect_left(P, q)
        ans += q * (len(P)-i)
    for p in P:
        i = bisect.bisect_right(Q, p)
        ans += p * (len(Q)-i)

    return ans


def main():
    W, H = read_int_n()
    P = [read_int() for _ in range(W)]
    Q = [read_int() for _ in range(H)]
    print(slv(W, H, P, Q))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(W, H, P, Q):
    W += 1
    H += 1
    ans = sum(P) + sum(Q)

    P.sort()
    Q.sort()
    
    for q in Q:
        i = bisect.bisect_left(P, q)
        
        ans += q * (len(P)-i)
    for p in P:
        i = bisect.bisect_right(Q, p)
        
        ans += p * (len(Q)-i)

    return ans


def main():
    W, H = read_int_n()
    P = [read_int() for _ in range(W)]
    Q = [read_int() for _ in range(H)]
    print(slv(W, H, P, Q))


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
w,h = map(int,input().split())
l = []
for i in range(w):
    p0 = int(input())
    l.append([-1*p0,0])
for i in range(h):
    q0 = int(input())
    l.append([-1*q0,1])
heapq.heapify(l)
wide = 0
high = 0
ans = 0
for i in range(w+h):
    a,b = heapq.heappop(l)
    if b == 0:
        ans += -1*a*(high+1)
        wide += 1
    else:
        ans += -1*a*(wide+1)
        high += 1
print(ans)

Solution (Python):
w,h = map(int,input().split())
pq = [[int(input()),0] for _ in range(w)] + [[int(input()),1] for _ in range(h)]
pq.sort()

a = w + 1
b = h + 1
ans = 0
for x,i in pq:
    if i == 0:
        ans += b*x
        a -= 1
    else:
        ans += a*x
        b -= 1

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10











































































def solve():
    w, h = LI()
    a = []
    x, y = 0, 1
    for _ in range(w):
        a.append((II(), x))
    for _ in range(h):
        a.append((II(), y))
    a.sort()
    plus_x = h + 1
    plus_y = w + 1
    ans = 0
    for ai, xy in a:
        if xy:
            ans += ai * plus_y
            plus_x -= 1
        else:
            ans += ai * plus_x
            plus_y -= 1
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    w,h=map(int,input().split())
    PQ=[None]*(w+h)
    for i in range(w):
        PQ[i]=(int(input()),0)
    for j in range(h):
        PQ[w+j]=(int(input()),1)
    PQ.sort()

    ans=0
    cnt=[h+1,w+1]
    for c,q in PQ:
        ans+=cnt[q]*c
        cnt[1-q]-=1
    print(ans)
resolve()

Solution (Python):
def main():
    import heapq
    w,h=map(int,input().split())
    p=[int(input()) for _ in [0]*w]
    q=[int(input()) for _ in [0]*h]
    
    cnt1=w+1
    cnt2=h+1

    h=[]
    heapq.heapify(h)
    for i in p:
        heapq.heappush(h,[i,0])
    for i in q:
        heapq.heappush(h,[i,1])

    ans=0
    while h:
        i,j=heapq.heappop(h)
        if j==0:
            ans+=cnt2*i
            cnt1-=1
        else:
            ans+=cnt1*i
            cnt2-=1
    print(ans)
main()

Solution (Python):
import sys
import heapq
from collections import defaultdict as dd
input = sys.stdin.readline
W, H = map(int, input().split())
pq = []
for _ in range(W): pq.append((int(input()), 0))
for _ in range(H): pq.append((int(input()), 1))
pq.sort(key = lambda x: -x[0])
a = W + 1
b = H + 1
res = 0
for _ in range(W + H):
  x = pq.pop()
  
  if x[1]:
    b -= 1
    res += a * x[0]
  else:
    a -= 1
    res += b * x[0]
  
print(res)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    w,h = LI()
    p = IR(w)
    q = IR(h)
    l = []
    for i in p:
        l.append([i,0])
    for i in q:
        l.append([i,1])
    x = 0
    y = 0
    l.sort()
    ans = 0
    for i,j in l:
        if j:
            ans += i*(w+1-x)
            y += 1
        else:
            ans += i*(h+1-y)
            x += 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
W, H = map(int, input().split())
p = [int(input()) for _ in range(W)]
q = [int(input()) for _ in range(H)]

pq = [(p[i], 0, i) for i in range(W)] + [(q[i], 1, i) for i in range(H)]
pq.sort()

ret = 0
x, y = W + 1, H + 1
for cost, type, i in pq :
    if type == 0 :
        x -= 1
        ret += p[i] * y
    else :
        y -= 1
        ret += q[i] * x
        
print(ret)

Solution (Python):
H, W = map(int, input().split())
P = [ int(input()) for _ in range(H) ]
Q = [ int(input()) for _ in range(W) ]
E = [(p, 0) for p in P] + [(q, 1) for q in Q]
E.sort()
ans = 0
for e in E:
  if e[1] == 0:
    ans += e[0] * (W+1)
    H -= 1
  if e[1] == 1:
    ans += e[0] * (H+1)
    W -= 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)]
PQ = P + Q
Idx = list(range(W+H))
Idx.sort(key=lambda x: PQ[x])
ans = 0
p = W+1
q = H+1
for idx in Idx:
    if idx >= W:
        ans += PQ[idx] * p
        q -= 1
    else:
        ans += PQ[idx] * q
        p -= 1
print(ans)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        
        if self._ranks[x] > self._ranks[y]:
            
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


W, H = list(map(int, sys.stdin.readline().split()))
P = [int(sys.stdin.readline()) for _ in range(W)]
Q = [int(sys.stdin.readline()) for _ in range(H)]


def test():
    edges = []
    vs = []
    for h, w in itertools.product(range(H + 1), range(W + 1)):
        if w < W:
            edges.append((P[w], (w, h), (w + 1, h)))
        if h < H:
            edges.append((Q[h], (w, h), (w, h + 1)))
    for h, w in itertools.product(range(H + 1), range(W + 1)):
        vs.append((w, h))
    edges.sort()

    
    uf = UnionFind(nodes=vs)
    ret = 0
    for s, v, u in edges:
        if uf.root(v) != uf.root(u):
            uf.unite(v, u)
            ret += s
    return ret



hs = P.copy()

vs = Q.copy()

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

ans = 0
v_nodes = W + 1
h_nodes = H + 1
while hs or vs:
    if not vs or (hs and hs[-1] < vs[-1]):
        
        
        ans += hs.pop() * h_nodes
        v_nodes -= 1
    else:
        
        ans += vs.pop() * v_nodes
        h_nodes -= 1
print(ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


W,H = list(map(int, sys.stdin.readline().split()))
P = [int(sys.stdin.readline()) for _ in range(W)]
Q = [int(sys.stdin.readline()) for _ in range(H)]

edges = []
for p in P:
    edges.append((p, 'P'))
for q in Q:
    edges.append((q, 'Q'))
edges.sort()

ans = 0
a = W + 1
b = H + 1
for e, pq in edges:
    if pq == 'P':
        ans += e * b
        a -= 1
    else:
        ans += e * a
        b -= 1
print(ans)

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

p.sort()

ps = [0,p[0]]
for i in range(1,w):
    ps.append(ps[-1]+p[i])

res = sum(p)
for e in q:
    k = bisect.bisect_right(p,e)
    res += e*(w-k+1) + ps[k]
print(res)

Solution (Python):
w,h=map(int,input().split())
e=[]
for _ in range(w):
  c=int(input())
  e.append((c,0))
for _ in range(h):
  c=int(input())
  e.append((c,1))
e=sorted(e,key=lambda x:x[0])
a=w+1
b=h+1
ans=0
for val,flag in e:
  if flag==0:
    ans+=val*b
    a-=1
  else:
    ans+=val*a
    b-=1
print(ans)

Solution (Python):
W, H = map(int, input().split())

side = [{"cost":int(input()), "di":0}for i in range(W)] + [{"cost":int(input()), "di":1}for i in range(H)]
side = sorted(side, key=lambda x:x["cost"])
ans = 0
ty = [H+1,W+1]
for s in side:
    cost, di = s["cost"], s["di"]
    ans += ty[di] * cost
    ty[(di+1)%2] -= 1
print(ans)

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

W, H = map(int, input().split())
costs = []
for _ in range(W):
    costs.append((int(input()), 0))
for _ in range(H):
    costs.append((int(input()), 1))
costs.sort(key=lambda x: x[0])

h = H+1
w = W+1
ans = 0
for cost, flg in costs:
    if flg == 0:
        ans += cost * h
        w -= 1
    else:
        ans += cost * w
        h -= 1
print(ans)

Solution (Python):
W, H = [int(_) for _ in input().split()]
S = []
for _ in range(W):
    S += [(int(input()), 0)]
for _ in range(H):
    S += [(int(input()), 1)]
S.sort()
ans = w = h = 0
for c, d in S:
    if d:
        ans += c * (W + 1 - w)
        h += 1
    else:
        ans += c * (H + 1 - h)
        w += 1
print(ans)

Solution (Python):
import sys
input=sys.stdin.buffer.readline
w,h=map(int,input().split())

L=[]

for i in range(w):
    n=int(input())
    L.append([n,0])
    
for i in range(h):
    n=int(input())
    L.append([n,1])
    
L.sort()

ans=0
for i in range(len(L)):
    if L[i][1]==0:
        ans+=L[i][0]*(h+1)
        w-=1
    else:
        ans+=L[i][0]*(w+1)
        h-=1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
w,h=map(int,input().split())

L=[]

for i in range(w):
    n=int(input())
    L.append([n,0])
    
for i in range(h):
    n=int(input())
    L.append([n,1])
    
L.sort()

ans=0
for i in range(len(L)):
    if L[i][1]==0:
        ans+=L[i][0]*(h+1)
        w-=1
    else:
        ans+=L[i][0]*(w+1)
        h-=1
print(ans)

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

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

P.sort()
Q.sort(reverse=True)

sP = [0]
a = 0
for p in P:
    a += p
    sP.append(a)

ans = sP[-1]
for q in Q:
    ip = bisect_left(P, q)
    ans += q*(W+1-ip) + sP[ip]
print(ans)

Solution (Python):
t,*p=open(0)
w,h=map(int,t.split()) 
c=0
for v,f in sorted((int(t),i<w)for i,t in enumerate(p)):
  c-=~h*v*f or~w*v
  w-=f
  h-=1^f
print(c)

Solution (Python):
t,*p=open(0)
w,h=map(int,t.split()) 
c=0
for v,f in sorted((int(t),i<w)for i,t in enumerate(p)):
  c-=~h*v*f or~w*v
  w-=f
  h-=1^f
print(c)

Solution (Python):
t,*p=open(0)
w,h=map(int,t.split()) 
c=0
for v,f in sorted((t,i<w)for i,t in enumerate(map(int,p))):
  c-=~h*v*f or~w*v
  w-=f
  h-=1^f
print(c)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

w,h = LI()
p = [I() for _ in range(w)]
q = [I() for _ in range(h)]
hq = []
for i in p:
    heappush(hq,(i,0))
for i in q:
    heappush(hq,(i,1))
ans = 0
w += 1
h += 1
while hq:
    v,flg = heappop(hq)
    if flg:
        ans += v*w
        h -= 1
    else:
        ans += v*h
        w -= 1
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
w,h = LI()
p = [I() for _ in range(w)]
q = [I() for _ in range(h)]
hq = []
for i in p:
    heappush(hq,(i,0))
for i in q:
    heappush(hq,(i,1))
ans = 0
w += 1
h += 1
while hq:
    v,flg = heappop(hq)
    if flg:
        ans += v*w
        h -= 1
    else:
        ans += v*h
        w -= 1
print(ans)

Solution (Python):
w,h=map(int,input().split())
s=sorted([[int(input()),0]for i in range(w)]+[[int(input()),1]for i in range(h)])
a,b,c=w+1,h+1,0
for i,j in s:
    if j:
        c+=i*a
        b-=1
    else:
        c+=i*b
        a-=1
print(c)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

cost = 0
rest_P = W
rest_Q = H
P.sort()
Q.sort()
INF = 10**10
P.append(INF)
Q.append(INF)
p = 0
q = 0
for _ in range(W+H):
    x,y = P[p],Q[q]
    if x < y:
        cost += x * (rest_Q+1)
        p += 1
        rest_P -= 1
    else:
        cost += y * (rest_P+1)
        q += 1
        rest_Q -= 1
print(cost)

Solution (Python):
import heapq
W, H = map(int, input().split())
Q = []
for _ in range(W):
  p = int(input())
  heapq.heappush(Q, [p, 0])
for _ in range(H):
  q = int(input())
  heapq.heappush(Q, [q, 1])
cnt = 0
L = [H + 1, W + 1]
while Q:
  c, l = heapq.heappop(Q)
  cnt += c * L[l]
  L[1 - l] -= 1
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

w, h = getList()

root = []
for i in range(w):
    n = getN()
    root.append((n, 0))

for i in range(h):
    n = getN()
    root.append((n, 1))

root.sort()
w += 1
h += 1
ans = 0
for r in root:
    if r[1] == 0:
        ans += r[0] * h
        w -= 1
    else:
        ans += r[0] * w
        h -= 1

print(ans)

Solution (Python):
w,h = map(int,input().split())
l = []
for _ in range(w):
  l.append((int(input()),0))
for _ in range(h):
  l.append((int(input()),1))
l.sort()
a = w+1
b = h+1
ans = 0
for p,t in l:
  if t:
    ans += p*a
    b -= 1
  else:
    ans += p*b
    a -= 1
print(ans)

Solution (Python):
W,H=map(int,input().split())
from heapq import heappush,heappop,heapify
p,q=[int(input()) for i in range(W)],[int(input()) for i in range(H)]
heapify(p),heapify(q)
r,i,j=0,W+1,H+1
while i>1 and j>1:
    if p[0]<q[0]:
        r+=heappop(p)*j
        i-=1
    else:
        r+=heappop(q)*i
        j-=1
print(r+sum(p)+sum(q))

Solution (Python):
W, H = map(int, input().split())

cost = [(int(input()), i, 'r') for i in range(W)] + [(int(input()), i, 'c') for i in range(H)]

cost.sort()
row = H + 1
col = W + 1
ans = 0

for c, i, t in cost:
    if t == 'r':
        ans += max(0, row) * c
        col -= 1
    else:
        ans += max(0, col) * c
        row -= 1

print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    width, high = map(int, input().split())
    cost_w = [int(input()) for i in range(width)]
    cost_h = [int(input()) for i in range(high)]

    cost_w.sort()
    cost_h.sort()
    check_high, check_width = 0, 0
    width_ind = 0
    ans = 0
    for i in range(high):

        now_high = cost_h[i]
        while width_ind < width:
            if now_high < cost_w[width_ind]:
                break
            ans += (high + 1 - check_high) * cost_w[width_ind]
            check_width += 1
            width_ind += 1

        ans += (width + 1 - check_width) * cost_h[i]
        check_high += 1

    ans += sum(cost_w[width_ind:])

    print(ans)







if __name__ == '__main__':
    main()

Solution (Python):
def getlist():
	return list(map(int, input().split()))

W, H = getlist()
E = []

for i in range(W):
	p = int(input())
	E.append([p, "W"])
for i in range(H):
	q = int(input())
	E.append([q, "H"])
E = sorted(E)

N = H + W
h = H + 1
w = W + 1
ans = 0
for i in range(N):
	if E[i][1] == "W":
		ans += E[i][0] * h
		w -= 1
	else:
		ans += E[i][0] * w
		h -= 1

print(ans)

Solution (Python):


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

import heapq

W,H = map(int,input().split())
PQ = []
for i in range(W+H+1):
    if i == W+1:
        continue
    pq = int(input())
    heapq.heappush(PQ,[pq,i,i+1])


w = W+1
h = H+1
ans = 0
V = [i for i in range(H+W+2)]

while PQ:
    e,s,t = heapq.heappop(PQ)
    if find(V,s) != find(V,t):
        union(V,s,t)
        if s < W: 
            ans+=(e*h)
            w-=1
        else:
            ans+=(e*w)
            h-=1
            
print(ans)

Solution (Python):
import sys,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

ans = 0
w,h = m()

p = []

for i in range(w):
    k = onem()
    p.append([k,0])
for i in range(h):
    k = onem()
    p.append([k,1])
p.sort()
w,h = w+1,h+1

for i in range(len(p)):
    if p[i][1] == 0:
        ans += h*p[i][0]
        w -= 1
    else:
        ans += w * p[i][0]
        h -= 1
print(ans)

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

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)


for i in range(W+H-1):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()

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

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W+H):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()

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

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W+H):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()

Solution (Python):
W,H=map(int,input().split())
p=sorted(int(input())for _ in'_'*W)
p+=10**18,
q=sorted(int(input())for _ in'_'*H)
q+=10**18,
z=i=j=0
h,w=H+1,W+1
while i<W or j<H:
	if p[i]<q[j]:
		z+=h*p[i]
		i+=1
		w-=1
	else:
		z+=w*q[j]
		j+=1
		h-=1
print(z)

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

for i in range(H):
    D.append((int(input()), 1))

D = sorted(D)
A, B = H + 1, W + 1
ans = 0
for i, k in D:
    if k == 0:
        ans += i * A
        B -= 1
    else:
        ans += i * B
        A -= 1

print(ans)

Solution (Python):
W,H = map(int,input().split())
PQ = [(int(input()),0) for _ in [0]*W] + [(int(input()),1) for _ in [0]*H]
PQ.sort()
r = H+1
c = W+1
ans = 0
for d,pq in PQ:
    if pq==0:
        ans += d*r
        c -=1
    else:
        ans += d*c
        r -=1
print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

w, h = map(int, input().split())
r = []
for _ in range(w):
	r.append([int(input()), 0])
for _ in range(h):
	r.append([int(input()), 1])
r.sort(key=lambda x: x[0], reverse=True)
p, q = h+1, w+1
ans, num = 0, 0
while num < (w+1)*(h+1)-1:
	x = r.pop()
	if x[1] == 0:
		num += p
		q -= 1
		ans += x[0]*p
	else:
		num += q
		p -= 1
		ans += x[0]*q

	if num > (w+1)*(h+1)-1:
		ans -= x[0] * (num-(w+1)*(h+1)+1)
print(ans)

Solution (Python):
from heapq import heappush, heappop


def main():
    W, H = map(int, input().split())
    h = []
    for _ in range(W):
        p = int(input())
        heappush(h, (p, 0))
    for _ in range(H):
        q = int(input())
        heappush(h, (q, 1))
    ans = 0
    while len(h):
        v, d = heappop(h)
        if d == 0:
            ans += v * (H+1)
            W -= 1
        else:
            ans += v * (W+1)
            H -= 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from functools import reduce


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


ans, _, _ = reduce(
    lambda acc, c: (
        (
            acc[0] + (H - acc[2] + 1) * c[0] if c[1] == 0 else
            acc[0] + (W - acc[1] + 1) * c[0]
        ),
        (
            acc[1] + 1 if c[1] == 0 else
            acc[1]
        ),
        (
            acc[2] + 1 if c[1] == 1 else
            acc[2]
        )
    ),
    sorted([(P, 0) for P in p] + [(Q, 1) for Q in q]),
    (0, 0, 0)
)


print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
w,h=map(int,input().split())
P=[float('inf')]+[int(input()) for _ in range(w)]
Q=[float('inf')]+[int(input()) for _ in range(h)]
P.sort(reverse=True); Q.sort(reverse=True)
ans=0
while w or h:
    if P[-1]<Q[-1] or (P[-1]==Q[-1] and w>=h):
        c=P.pop()
        ans+=c*(h+1)
        w-=1
    else:
        c=Q.pop()
        ans+=c*(w+1)
        h-=1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
W,H=map(int,input().split())
P=[int(input()) for _ in range(W)]+[float('inf')]
Q=[int(input()) for _ in range(H)]+[float('inf')]
P.sort(reverse=True)
Q.sort(reverse=True)
ans=0
W+=1
H+=1
while True:
    if W==H==1:
        break
    elif Q[-1]<P[-1] or (Q[-1]==P[-1] and W<=H):
        ans+=W*Q[-1]
        H-=1
        Q.pop()
    elif Q[-1]>P[-1] or (Q[-1]==P[-1] and W>H):
        ans+=H*P[-1]
        W-=1
        P.pop()
print(ans)

Solution (Python):
from heapq import heapify, heappop
w,h = map(int, input().split())
heap = []
for i in range(w):
    p = int(input())
    heap.append((p,0))
for i in range(h):
    q = int(input())
    heap.append((q,1))
heapify(heap)

ans = 0
h += 1
w += 1
while heap:
    c, f = heappop(heap)
    if f==0:
        ans += c*h
        w -= 1
    else:
        ans += c*w
        h -= 1
print(ans)

Solution (Python):
import sys, math, collections, heapq, itertools
from bisect import bisect
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    X, Y = map(int, line_input())
    p = [0] * X

    total_cost = 0
    for x in range(X): 
        p[x] = int(single_input())
        total_cost += p[x]
    p.sort()    
    total_sum_p = [0] * (X + 1)
    for x in range(X):
        total_sum_p[x+1] = total_sum_p[x] + p[x]
    
    for y in range(Y): 
        q = int(single_input())
        total_cost += q
        x_smaller_than_y = bisect(p, q)
        total_cost += q * (X - x_smaller_than_y) + total_sum_p[x_smaller_than_y]

    return total_cost
  
if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys, math, collections, heapq, itertools
from bisect import bisect
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b
  
def solve():
    X, Y = map(int, line_input())
    p = [0] * X
    q = [0] * Y
    for x in range(X): p[x] = int(single_input())
    for y in range(Y): q[y] = int(single_input())
    total_cost = sum(p) + sum(q)
    p.sort()
    total_sum_p = [0] * (X + 1)
    for x in range(X):
        total_sum_p[x+1] = p[x] + total_sum_p[x]
    for y in range(Y):
        x_smaller_than_y = bisect(p, q[y])
        total_cost += q[y] * (X - x_smaller_than_y) + total_sum_p[x_smaller_than_y]
    return total_cost
  
if __name__ == "__main__":
    print(solve())