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):
W,H = (int(num) for num in input().split())
p = [int(input()) for _ in range(W)]
p.sort()
q = [int(input()) for _ in range(H)]
q.sort()
p_cnt = H+1 
q_cnt = W+1
gr_cnt = (W+1) * (H+1) - 1
p_idx = 0
q_idx = 0
ans = 0

while gr_cnt > 0:
    if (p_idx < W and q_idx < H and p[p_idx] <= q[q_idx]) or q_idx >= H:
        nt = min(p_cnt,gr_cnt)
        
        ans += p[p_idx] * nt
        gr_cnt -= nt
        q_cnt -= 1
        p_idx += 1
    elif (p_idx < W and q_idx < H and p[p_idx] > q[q_idx]) or p_idx >= W:
        nt = min(q_cnt,gr_cnt)
        
        ans += q[q_idx] * nt
        gr_cnt -= nt
        p_cnt -= 1
        q_idx += 1
    
        
print(ans)

Solution (Python):
w, h = map(int, input().split())

w_cost = [int(input()) for i in range(w)]
h_cost = [int(input()) for i in range(h)]

w_cost = sorted(w_cost, reverse = True)
h_cost = sorted(h_cost, reverse = True)
w_cnt = 0
h_cnt = 0
ans = 0

while True:
    if not w_cost:
        ans += sum(h_cost)   
        break
    elif not h_cost:
        ans += sum(w_cost)
        break
    elif w_cost[-1] < h_cost[-1]:
        ans += w_cost[-1] * (h+1-h_cnt)
        w_cnt += 1
        del w_cost[-1]
    else:
        ans += h_cost[-1] * (w+1-w_cnt)
        h_cnt += 1
        del h_cost[-1]
        
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

W,H=MAP()
P=[(INT(), 'p') for i in range(W)]
Q=[(INT(), 'q') for i in range(H)]


PQ=P+Q
PQ.sort()

a=H+1
b=W+1
ans=0
for i in range(W+H):
    val,_type=PQ[i]
    if _type=='p':
        
        ans+=a*val
        b-=1
    else:
        
        ans+=b*val
        a-=1
print(ans)

Solution (Python):


import sys
from bisect import bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

W,H=MAP()
P=[INT() for i in range(W)]
Q=[INT() for i in range(H)]

P.sort()
Q.sort()

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

Solution (Python):
W,H=map(int,input().split())
P=[int(input()) for i in range(W)]
Q=[int(input()) for j in range(H)]
P.append(float('inf'))
Q.append(float('inf'))
P.sort(reverse=True)
Q.sort(reverse=True)
now_W=W+1
now_H=H+1
cost=0
while now_W>1 or now_H>1:
    if P[-1]<Q[-1]:
        cost+=P.pop()*now_H
        now_W-=1
    elif Q[-1]<P[-1]:
        cost+=Q.pop()*now_W
        now_H-=1
    elif P[-1]==Q[-1]:
        if now_W<=now_H:
            cost+=Q.pop()*now_W
            now_H-=1
        elif now_W>now_H:
            cost+=P.pop()*now_H
            now_W-=1
print(cost)

Solution (Python):
from itertools import accumulate
from bisect import bisect_left
W, H = map(int, input().split())
W_cost = sorted([int(input()) for i in range(W)])
H_cost = [int(input()) for i in range(H)]



W_cost_sum = sum(W_cost)
ans = W_cost_sum * (H + 1) + sum(H_cost)


W_acc_cost = [0] + list(accumulate(W_cost))
for h in H_cost:
    hx = bisect_left(W_cost, h)
    ans -= (W_cost_sum - W_acc_cost[hx]) - ((W - hx) * h)

print(ans)

Solution (Python):
import sys

W, H = map(int, input().split())
Xs = [int(sys.stdin.readline()) for _ in range(W)] + [10**9]
Ys = [int(sys.stdin.readline()) for _ in range(H)] + [10**9]

Xs.sort()
Ys.sort()

ans = 0
iX = iY = 0
for _ in range(W+H):
    if Xs[iX] <= Ys[iY]:
        ans += Xs[iX] * (H-iY+1)
        iX += 1
    else:
        ans += Ys[iY] * (W-iX+1)
        iY += 1

print(ans)

Solution (Python):
W, H = (int(i) for i in input().split())
L = []
for i in range(W):
  L.append((int(input()), 0))
for i in range(H):
  L.append((int(input()), 1))
a = W
b = H
ans = 0
L.sort()
for i in range(H + W):
  if L[i][1] == 0:
    ans += (b+1) * L[i][0]
    a -= 1
  else:
    ans += (a+1) * L[i][0]
    b -= 1
print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[w,h]=i2()
p=[]
q=[]
import bisect
for i in range(w):
 p.append(i1())
for i in range(h):
 q.append(i1())
x=p[:]
x.sort()
d=[x[i] for i in range(w)]
for i in range(w-1):
  d[i+1]+=d[i]
ans=0
for i in range(h):
 dd=bisect.bisect_right(x,q[i])
 if dd>0:
    ans+=d[dd-1]

 ans+=(w-dd)*q[i]
for i in range(h):
 ans+=q[i]
print(ans+d[w-1])

Solution (Python):
W,H=map(int,input().split())
List=[]
for i in range(W):
  p=int(input())
  List.append((p,"W"))
for j in range(H):
  q=int(input())
  List.append((q,"H"))
ans=0
List.sort()
for a,l in List:
  if l=="W":
    ans+=(H+1)*a
    W-=1
  elif l=="H":
    ans+=(W+1)*a
    H-=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)]
c=sorted([(i,0) for i in p]+[(j,1) for j in q])
a=W+1
b=H+1
ans=0
for z in c:
    if z[1]==0:
        ans+=z[0]*b
        a-=1
    else:
        ans+=z[0]*a
        b-=1
print(ans)

Solution (Python):

import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


W, H = map(int, input().split())
p = []
for i in range(W):
    p.append(int(input()))
q = []
for j in range(H):
    q.append(int(input()))


a = []
for i in range(W):
    a.append(("p", i, p[i]))
for j in range(H):
    a.append(("q", j, q[j]))


a.sort(key=lambda x: x[2])


p_used = 0
q_used = 0
count = 0
cost = 0
i = 0
while True:
    now = a[i]
    if now[0] == "p":
        now_count = H+1 - q_used
        if count + now_count > (W+1)*(H+1) - 1:
            now_count = (W+1)*(H+1) - 1 - count
        count += now_count
        cost += now[2] * now_count
        p_used += 1
    else:
        now_count = W+1 - p_used
        if count + now_count > (W+1)*(H+1) - 1:
            now_count = (W+1)*(H+1) - 1 - count
        count += now_count
        cost += now[2] * now_count
        q_used += 1
    if count == (W+1)*(H+1) - 1:
        break
    i += 1
debug(count)
print(cost)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

W, H = inpl()
p = [(int(input()), 0) for _ in range(W)]
q = [(int(input()), 1) for _ in range(H)]
pq = sorted(p+q)
cW = W+1
cH = H+1
ans = 0
for i, j in pq:
    if j == 1:
        ans += i*cW
        cH -= 1
    else:
        ans += i*cH
        cW -= 1
print(ans)

Solution (Python):
W,H=map(int,input().split())
p=[(int(input()),0) for i in range(W)]
q=[(int(input()),1) for i in range(H)]
r=sorted(p+q)
a=W+1
b=H+1
ans=0
for seq in r:
    wt,idx=seq
    if idx==0:
        a-=1
        ans+=b*wt
    else:
        b-=1
        ans+=a*wt
print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


w,h = li()
stack = []
for _ in range(w):
    stack.append((ni(),0))
    
for _ in range(h):
    stack.append((ni(),1))
    
    
stack.sort(reverse=True)

res_w = 0
res_h = 0

ans = 0

while res_w <= w and res_h <= h and stack:
    cost, wh = stack.pop()

    if wh == 0:
        ans += (cost * ((h+1)-res_h))
        res_w += 1
        
    else:
        ans += (cost * ((w+1)-res_w))
        res_h += 1

        
print(ans)

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

E = sorted(P + Q)
used = [W + 1, H + 1]

ans = 0
for e, f in E:
    ans += e * used[1 - f]
    used[f] -= 1

print(ans)

Solution (Python):
w,h=map(int,input().split())
n=lambda :int(input())
pq=[]
for _ in range(w):
  pq.append((n(),0))
for _ in range(h):
  pq.append((n(),1))
pq.sort()
w,h=w+1,h+1
ans=0
for i,j in pq:
  if j:
    ans+=i*w
    h-=1
  else:
    ans+=i*h
    w-=1
print(ans)

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

es = []
for p in ps:
    es.append((p,0))
for q in qs:
    es.append((q,1))
es.sort()

ans = 0
xn,yn = W+1,H+1
for d,t in es:
    if t:
        ans += d * xn
        yn -= 1
    else:
        ans += d * yn
        xn -= 1
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

W,H = inpl()
Lines = []
for i in range(W):
	Lines.append([int(input()),True])
for i in range(H):
	Lines.append([int(input()),False])

Lines.sort()
X = Y = 0
ans = 0
for c,xy in Lines:
	if xy:
		ans += c*(H+1-Y)
		X += 1
	else:
		ans += c*(W+1-X)
		Y += 1

print(ans)

Solution (Python):
w,h = list(map(int,input().split()))
pq = []
for i in range(w):
    pq.append((int(input()),0))
for i in range(h):
    pq.append((int(input()),1))
pq.sort()
res = 0
w+=1
h+=1
dic = {0:w,1:h}

for x in pq:
    res += dic[1-x[1]]*x[0]
    dic[x[1]] -= 1

print(res)

Solution (Python):
from numpy import *
from scipy import *
from sys import *

w, h = map(int, input().split())
p = array([int(input()) for i in range(w)])
q = array([int(input()) for i in range(h)])
p = append(p, maxsize)
q = append(q, maxsize)

p, q = sort(p), sort(q)

ans = 0

i, j = 0, 0
w_, h_ = w+1, h+1
while i < w or j < h:
    if p[i] < q[j]:
        ans += p[i]*h_
        w_ -= 1
        i += 1
    else:
        ans += q[j]*w_
        h_ -= 1
        j += 1

print(ans)

Solution (Python):
from numpy import *
from scipy import *
from sys import *

w, h = map(int, input().split())
p = ndarray(w+1, dtype=int)
q = ndarray(h+1, dtype=int)

for i in range(w):
    p[i] = int(input())
for i in range(h):
    q[i] = int(input())
p[w] = maxsize
q[h] = maxsize
p, q = sort(p), sort(q)

ans = 0

i, j = 0, 0
w_, h_ = w+1, h+1
while i < w or j < h:
    if p[i] < q[j]:
        ans += p[i]*h_
        w_ -= 1
        i += 1
    else:
        ans += q[j]*w_
        h_ -= 1
        j += 1

print(ans)

Solution (Python):
w,h = map(int,input().split())
p = list(sorted([int(input()) for i in range(w)],reverse=True))
q = list(sorted([int(input()) for i in range(h)],reverse=True))

steps = w+h
w += 1; h += 1
ret = 0
for i in range(steps):
    if w == 1 or h != 1 and p[-1] > q[-1]:
        ret += w * q.pop()
        h -= 1
    else:
        ret += h * p.pop()
        w -= 1
print(ret)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    w,h = LI()
    p = sorted([I() for _ in range(w)])
    q = sorted([I() for _ in range(h)])
    r = 0
    pi = 0
    qi = 0
    for i in range(w+h):
        if qi == h:
            r += p[pi] * (h-qi+1)
            pi += 1
        elif pi == w:
            r += q[qi] * (w-pi+1)
            qi += 1
        elif p[pi] < q[qi]:
            r += p[pi] * (h-qi+1)
            pi += 1
        else:
            r += q[qi] * (w-pi+1)
            qi += 1

    return r

print(main())

Solution (Python):
import heapq

pq = []


W, H = map(int, input().split())
for i in range(W):
	heapq.heappush(pq, (int(input()), 'W'))
for i in range(H):
	heapq.heappush(pq, (int(input()), 'H'))

W += 1
H += 1

ans = 0
while pq:
	(num, dire) = heapq.heappop(pq)
	if dire == 'W':
		ans += num * H
		W -= 1
	else:
		ans += num * W
		H -= 1

print(ans)

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

ans=0
for a in arr:
    if a[1]=='p':
        ans+=a[0]*(h+1)
        w-=1
    else:
        ans+=a[0]*(w+1)
        h-=1
print(ans)

Solution (Python):
W, H = map(int, raw_input().split())
 
p_list = list()
q_list = list()
 
for i in range(W):
    p_list.append(int(raw_input()))
    
for j in range(H):
    q_list.append(int(raw_input()))
 
p_list.sort()
q_list.sort()
 
cp = H+1
cq = W+1
 
res = 0
pid = 0
qid = 0
 
while True:
    if pid == W:
        if qid == H:
            break
        else:
            choice = 'q'
    elif qid == H:
        choice = 'p'
    elif p_list[pid] < q_list[qid]:
        choice = 'p'
    else:
        choice = 'q'
    if choice == 'p':
        cq -= 1
        res += cp*p_list[pid]
        pid += 1
    else:
        cp -= 1
        res += cq*q_list[qid]
        qid += 1
 
print res

Solution (Python):



from __future__ import division, print_function, absolute_import, unicode_literals

W, H = map(int, input().split())
cx = 0
cy = 0
P = [(i, int(input()), 'W') for i in range(W)]
Q = [(i, int(input()), 'H') for i in range(H)]

PQ = sorted(P+Q, key=lambda x: x[1])
ans = 0
for index, cost, wh in PQ:
    if wh == 'W':
        cx += 1
        ans += cost * (H + 1 - cy)
    elif wh == 'H':
        cy += 1
        ans += cost * (W + 1 - cx)
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)]

P.sort()
Q.sort()

ans = 0
for p in P:
    ind = bisect.bisect_right(Q, p)
    ans += p * (H - ind + 1)
for q in Q:
    ind = bisect.bisect_left(P, q)
    ans += q * (W - ind + 1)
print(ans)

Solution (Python):
from collections import deque
W, H = map(int, input().split())
pandq = []
for i in range(W):
	pandq.append([int(input()),"p"])
for i in range(H):
	pandq.append([int(input()),"q"])
sortedCost = deque(sorted(pandq))

a = W + 1
b = H + 1
totalcosts = 0
while sortedCost:
	cost = sortedCost.popleft()
	if cost[1] == "p":
		totalcosts += cost[0] * b
		a -= 1
	else:
		totalcosts += cost[0] * a
		b -= 1
print(totalcosts)

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

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

def r(xy):
    if xy == 0:
        return 1
    return 0

WH = (W + 1, H + 1)
C = [0, 0]
answer = 0
for w, xy in edges:
    C[xy] += 1
    n = WH[r(xy)] - C[r(xy)]
    answer += n * w
print(answer)

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

p_list = list()
q_list = list()

for i in range(W):
    p_list.append(int(raw_input()))
    
for j in range(H):
    q_list.append(int(raw_input()))

p_list.sort()
q_list.sort()

cp = H+1
cq = W+1

res = 0
pid = 0
qid = 0

while True:
    if pid == W:
        if qid == H:
            break
        else:
            choice = 'q'
    elif qid == H:
        choice = 'p'
    elif p_list[pid] < q_list[qid]:
        choice = 'p'
    else:
        choice = 'q'
    if choice == 'p':
        cq -= 1
        res += cp*p_list[pid]
        pid += 1
    else:
        cp -= 1
        res += cq*q_list[qid]
        qid += 1

print res

Solution (Python):
w,h=map(int,raw_input().split())
p=[[int(raw_input()),0] for _ in xrange(w)]
q=[[int(raw_input()),1] for _ in xrange(h)]
pq=p+q
pq.sort()
a=w+1
b=h+1
ans=0
for i in xrange(w+h):
    if pq[i][1]==0:
        ans+=b*pq[i][0]
        a-=1
    else:
        ans+=a*pq[i][0]
        b-=1

print(ans)

Solution (Python):
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    w, h = reads()
    p = sorted([read() for _ in range(w)])[::-1]
    q = sorted([read() for _ in range(h)])[::-1]

    pi = w-1
    qi = h-1
    res = 0
    while 0<=pi and 0<=qi:
        if p[pi] < q[qi]:
            res += p[pi] * (h+1)
            pi -= 1
            w -= 1
        else:
            res += q[qi] * (w+1)
            qi -= 1
            h -= 1
    res += sum(p[:pi+1]) + sum(q[:qi+1])
    print(res)

main()

Solution (Python):
W,H = map(int,raw_input().split(" "))
V = max(W,H)


PI = [input() for i in range(W)]
QI = [input() for i in range(H)]

   
ans = sum(PI)*(H+1)+sum(QI)*(W+1)


PI.sort(reverse=True)
QI.sort(reverse=True)

if W < V:
    for i in range(V-W):
        PI.append(0)
if H < V:
    for i in range(V-H):
        QI.append(0)
 

cnt = W*H

WW = H
HH = W



pin = 0
qin = 0


while cnt:

    if PI[pin] > QI[qin]:
        ans -= PI[pin] * WW
        HH-=1
        cnt -= WW
        pin += 1
    else:
        ans -= QI[qin] * HH

        WW-=1
        cnt -= HH
        qin+=1
print ans

Solution (Python):
w, h = map(int, raw_input().split())
p = []
q = []
for i in xrange(w):
    p.append(int(raw_input()))
for i in xrange(h):
    q.append(int(raw_input()))

wl = w
hl = h

cost = 0

p.sort()
q.sort()

p.append(10 ** 8 + 1)
q.append(10 ** 8 + 1)

pc = 0
qc = 0

while(wl + hl - pc - qc> 0):
    if p[pc] < q[qc]:
        cost += (hl - qc + 1) * p[pc]
        pc += 1
    else:
        cost += (wl - pc + 1) * q[qc]
        qc += 1

print cost

Solution (Python):
ss=raw_input().split()
w=int(ss[0])
h=int(ss[1])

a=[]
b=[]

for i in xrange(w):
    p=input()
    a.append(p)
for i in range(h):
    p=input()
    b.append(p)

a.sort()
b.sort()

h1=0
h2=0
res=0

while h1 < w and h2 < h:
    if a[h1]<b[h2]:
        res += a[h1] * (h - h2 + 1)
        h1 += 1
    else:
        res += b[h2] * (w - h1 + 1)
        h2 += 1
while (h1<w):
    res += a[h1]
    h1 += 1
while (h2<h):
    res += b[h2]
    h2 += 1
print res

Solution (Python):

import bisect
cost = 0
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
sum_p = []
for i in xrange(W):
    tmp = int(raw_input())
    p.append((i, tmp))
p.sort(key=lambda a: a[1])
pp = [each[1] for each in p]
for i in xrange(W):
    if not sum_p:
        sum_p.append(pp[i])
    else:
        sum_p.append(sum_p[-1]+pp[i])
cost += sum(pp)
for j in xrange(H):
    new = int(raw_input())
    cost += new
    minus = bisect.bisect_right(pp, new)
    cost += (W-minus) * new
    cost += sum_p[minus-1] if minus > 0 else 0

print cost

Solution (Python):
ss=raw_input().split()
w=int(ss[0])
h=int(ss[1])
a=[]
b=[]
for i in range( w):
    p=input()
    a.append( p)
for i in range( h):
    p=input()
    b.append( p)
a.sort()
b.sort()
h1=0
h2=0
ans=0
while ((h1<w) and (h2<h)):
    if a[h1]<b[h2]:
        ans+=a[h1]*(h - h2+1)
        h1+=1
    else :
        ans += b[h2] * (w-h1+1)
        h2 += 1
while (h1<w):
    ans+=a[h1]
    h1+=1
while (h2<h):
    ans+=b[h2]
    h2+=1
print ans

Solution (Python):
ss=raw_input().split()
w=int(ss[0])
h=int(ss[1])
a=[]
b=[]
for i in range(w):
    p=input()
    a.append(p)
for i in range(h):
    p=input()
    b.append(p)
a.sort()
b.sort()
h1=0
h2=0
ans=0
while ((h1<w) and (h2<h)):
    if a[h1]<b[h2]:
        ans+=a[h1]*(h - h2+1)
        h1+=1
    else :
        ans += b[h2] * (w-h1+1)
        h2 += 1
while (h1<w):
    ans+=a[h1]
    h1+=1
while (h2<h):
    ans+=b[h2]
    h2+=1
print ans

Solution (Python):
w,h= map(int, raw_input().split())
p =[]
q = []
for i in xrange(w):
    t = input()
    p.append(t)

for i in xrange(h):
    t = input()
    q.append(t)
p =sorted(p,reverse=True)
q =sorted(q, reverse=True)
ac = p[:]
acq = q[:]
i = w-2
while i >=0:
    ac[i] += ac[i+1]
    i -=1
i = h - 2
while i >= 0:
    acq[i] += acq[i + 1]
    i -= 1
c = ac[0] + acq[0]
k = 0

i = 0
while i < h:
    
        j = k
        
        if j >= w:
            break
        if q[i] > p[j]:
            c += ac[j]
            i += 1
            
        else:
            c +=acq[i]
            k +=1
        
print c

Solution (Python):
import numpy as np
w, h = map(int, input().split())
ps = [int(input()) for _ in range(w)]
qs = np.sort([int(input()) for _ in range(h)])
sqs = np.cumsum(qs)
bound = np.searchsorted(qs, ps)

s = sum(qs) + sum(ps)

for p, b in zip(ps, bound):
    if b > 0:
        s += sqs[b-1] + p*(h-b)
    else:
        s += p*h

print(s)

Solution (Python):
W, H = map(int, raw_input().split())
p = sorted([(i, int(raw_input())) for i in xrange(W)], key=lambda x:-x[1])
q = sorted([(i, int(raw_input())) for i in xrange(H)], key=lambda x:-x[1])
ans = 0
pe, qe, ae = 0, 0, (W+1)*(H+1)-1
while len(p)> 0 or len(q) > 0:
    if len(q) == 0 or (len(p) > 0 and p[-1][1] <= q[-1][1]):
        i, cost = p.pop()
        pe += 1
        ans += cost*(H+1-qe)
    else:
        j, cost = q.pop()
        qe += 1
        ans += cost*(W+1-pe)

print ans

Solution (Python):




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





is_connected_X = [False for _ in range(W)]
count_connected_X = 0
is_connected_Y = [False for _ in range(H)]
count_connected_Y=0

P = [(i,int(input()),"W") for i in range(W)]
Q = [(j,int(input()),"H") for j in range(H)]

PQ = sorted(P+Q, key=lambda x:x[1])

total_cost=0
for i,cost,wh in PQ:

    if wh=="W":
        count_connected_X+=1
        is_connected_X[i]=True
        total_cost+= cost*(H+1-count_connected_Y)
    elif wh=="H":
        count_connected_Y += 1
        is_connected_Y[i] = True
        total_cost += cost * (W + 1 - count_connected_X)

print(total_cost)

Solution (Python):
W, H = list(map(int, input().split()))
p = sorted([int(input()) for _ in range(W)], reverse=True)
q = sorted([int(input()) for _ in range(H)], reverse=True)
ans = 0
while len(p) > 0 and len(q) > 0:
    
    if p[-1] < q[-1]:
        ans += p[-1] * (H + 1)
        
        p.pop()
        W -= 1
    else:
        ans += q[-1] * (W + 1)
        
        q.pop()
        H -= 1
ans += sum(p) + sum(q)
print(ans)

Solution (Python):
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

cost = sum(pw) * (h + 1) + sum(ph) * (w + 1)

phc = sorted(ph)
pwc = sorted(pw)

for i in range(w):
    index = bisect.bisect_left(phc, pw[i])
    cost -= pw[i] * index

for i in range(h):
    index = bisect.bisect_right(pwc, ph[i])
    cost -= ph[i] * index

print cost

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9


def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

W, H = ln()

usedC = 0
usedR = 0

candidate = []

for i in xrange(W):
    candidate.append((n(), i, 0))
for i in xrange(H):
    candidate.append((n(), i, 1))


candidate.sort()


result = 0
for cost, i, type in candidate:
    if type == 1:
        result += (W + 1 - usedC) * cost
        usedR += 1
    else:
        result += (H + 1 - usedR) * cost
        usedC += 1

print result

Solution (Python):
x = raw_input()
w,h = [int(i) for i in x.split()]
p = []
for i in range(w):
    p.append(input())
q = []
for i in range(h):
    q.append(input())
cost = 0
p.sort()
q.sort()
iter = w+h

p_iter = 0
q_iter = 0
for i in range(iter):
    if(w==0):
        cost += q[q_iter]*(w+1)
        h -= 0
        q_iter += 1

    elif(h==0):
        cost += p[p_iter]*(h+1)
        w -= 0
        p_iter += 1

    elif(p[p_iter]==q[q_iter] and h>w):
        cost += p[p_iter]*(h+1)
        w -= 1
        p_iter += 1

    elif(p[p_iter]<q[q_iter]):
        cost += p[p_iter]*(h+1)
        w -= 1
        p_iter += 1
    
    else:
        cost += q[q_iter]*(w+1)
        h -= 1
        q_iter += 1
    
print cost

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

W, H = map(int, raw_input().split())
p = [int(raw_input()) for i in xrange(W)]
q = [int(raw_input()) for i in xrange(H)]
r = zip(p, [0]*W) + zip(q, [1]*H)
r.sort(reverse = True)
w, h = 0, 0
ans = sum(p)*(H + 1) + sum(q)*(W + 1) 
for x, k in r:
    if k == 0:
        ans -= max(0, (H - h)*x)
        w += 1
    else:
        ans -= max(0, (W - w)*x)
        h += 1
print ans

Solution (Python):
w, h = map(int, raw_input().split())
P = [int(raw_input()) for i in xrange(w)]
Q = [int(raw_input()) for i in xrange(h)]

P.sort()
Q.sort()

cp = cq = 0
ans = 0
while cp < w and cq < h:
    
    if P[cp] < Q[cq]:
        
        ans += P[cp] * (h+1-cq)
        cp += 1
    else:
        
        ans += Q[cq] * (w+1-cp)
        cq += 1
while cp < w:
    ans += P[cp] * (h+1-cq)
    cp += 1
while cq < h:
    ans += Q[cq] * (w+1-cp)
    cq += 1

print ans