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



Sample input:
2 2
3
5
2
7


Sample output:
29

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
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 = []
#column: 0, row: 1
for i in xrange(W):
    candidate.append((n(), i, 0))
for i in xrange(H):
    candidate.append((n(), i, 1))

#print candidate
candidate.sort()
#print candidate

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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

Submission status: Accepted

Solution code:
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:
    #print cp, cq, ans
    if P[cp] < Q[cq]:
        #print P[cp]
        ans += P[cp] * (h+1-cq)
        cp += 1
    else:
        #print Q[cq]
        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

Submission status: Runtime Error

Solution code:
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 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)

Submission status: Runtime Error

Solution code:
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 not p or p[-1]>q[-1]:
    ans+=q.pop()*c
    r-=1
  else:
    ans+=p.pop()*r
    c-=1
print(ans)

Submission status: Runtime Error

Solution code:

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):
    #print(ans, remainW, remainH)
    costW = ws[remainW-1] * (remainH + 1)
    costH = hs[remainH-1] * (remainW + 1)
    if(ws[remainW-1] > hs[remainH-1] or remainW==0):
        ans += costH
        remainH-=1
    else:
        ans += costW
        remainW -= 1
print(ans)

Submission status: Runtime Error

Solution code:

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):
    #print(ans, remainW, remainH)
    costW = ws[remainW-1] * (remainH + 1)
    costH = hs[remainH-1] * (remainW + 1)
    if(costW > costH or remainW==0):
        ans += costH
        remainH-=1
    else:
        ans += costW
        remainW -= 1
print(ans)

Submission status: Runtime Error

Solution code:
W,H=[int(item) for item in input().split()]
p=[]
for _ in range(W):
    p.append(int(input()))

q=[]
for _ in range(H):
    q.append(int(input()))

cost = [[114514] * (W+1) for i in range(H+1)]
cost[0][0]=0
cnt = 1
totalcost=0
while True:
    if cnt <= H :
        x,y=0,cnt
    else:
        x,y=cnt-H,H
        if cnt-H==W+1:break
    while y>=0 and x<=W:
        if x == 0:
            cost[x][y]=cost[x][y-1]+q[y-1]
            totalcost+=q[y-1]
        elif y == 0:
            cost[x][y]=cost[x-1][y]+p[x-1]
            totalcost+=p[x-1]
        else:
            totalcost += p[x - 1] if p[x - 1] < q[y - 1] else q[y-1]
            # if cost[x][y - 1] + q[y - 1] < cost[x - 1][y] + p[x - 1]:
            #    cost[x][y]=cost[x][y-1]+q[y-1]
            #    totalcost+=q[y-1]
            # else:
            #    cost[x][y]=cost[x-1][y]+p[x-1]
            #    totalcost += p[x - 1]
        #print(x,y)
        x += 1
        y -= 1
    #print(cnt)
    #print(cost)
    cnt += 1
print(totalcost)

Submission status: Runtime Error

Solution code:
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 (p<W and P[p]<Q[q]) or 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()

Submission status: Runtime Error

Solution code:
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 p<W and P[p]<Q[q] or 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()

Submission status: Runtime Error

Solution code:
#C問題
#UnionFind
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

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


uf = UnionFind(H+W+2)
a = W+1
b = H+1
ans = 0
V = [i for i in range(H+W+2)]

while PQ:
    edge = heapq.heappop(PQ)
    w,s,t = edge[0],edge[1],edge[2]
    if find(V,s) != find(V,t):
        union(V,s,t)
        if s < W+1: #P
            ans+=w*b
            a-=1
        else:#Q
            ans+=w*a
            b-=1
            
print(ans)

Submission status: Runtime Error

Solution code:
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)
#1マスずつmax(pi,qj)→O(N^2)
#pi,qjが大きい順に列ごと消去→O(N)
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()
  print(p,q)

Submission status: Runtime Error

Solution code:
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()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
print(ans)

Submission status: Runtime Error

Solution code:
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 p[p_idx] <= q[q_idx]) or q_idx >= H:
        nt = min(p_cnt,gr_cnt)
        #print(gr_cnt,nt,p[p_idx])
        ans += p[p_idx] * nt
        gr_cnt -= nt
        q_cnt -= 1
        p_idx += 1
    else:
        nt = min(q_cnt,gr_cnt)
        #print(gr_cnt,nt,q[q_idx])
        ans += q[q_idx] * nt
        gr_cnt -= nt
        p_cnt -= 1
        q_idx += 1
    
        
print(ans)

Submission status: Runtime Error

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

p.sort(reverse=True)
q.sort(reverse=True)

cost=0
del_H=0
del_W=0
len_p=W
len_q=H

while len_p>0 and len_q>0:
    
    if p[del_W]>q[del_H]:
        del_W+=1
        cost+=p[del_W]*(del_H+1)
        len_p-=1
    else:
        del_H+=1
        cost+=q[del_H]*(del_W+1)
        len_q-=1
        

if len_p==0:
    cost+=sum(q)*(W+1)

else:
    cost+=sum(p)*(H+1)

print cost

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
from networkx import nx
import sys

def build_graph(W, H, p, q):
    graph = nx.Graph()
    for i in range(W):
        for j in range(H):
            x = j*W + i
            if i+1 < W:
                graph.add_edge(x, x+1, weight=p[i])
            if j+1 < H:
                graph.add_edge(x, x+W, weight=q[j])
    return graph


def prim(G, s):
    P, Q = {}, [(0, None, s)]   
    while Q:
        _, p, u = heappop(Q)
        if u in P: continue
        P[u] = p
        for v, w in G[u].items():
            heappush(Q, (w, u, v))
    return sum(G[key][P[key]]['weight'] for key in P if P[key] != None)

W, H = map(int, raw_input().split(' '))
p = [0] * W
q = [0] * H
for i in xrange(W):
    p[i] = int(raw_input())
for j in xrange(H):
    q[j] = int(raw_input())
W+=1
H+=1
g = build_graph(W, H, p, q)
p = prim(g, 0)
print p

Submission status: Runtime Error

Solution code:
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 == H:
        if qid == W:
            break
        else:
            choice = 'q'
    elif qid == W:
        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

Submission status: Runtime Error

Solution code:
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)
q.append(10 ** 8)

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

Submission status: Runtime Error

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

wl = w
hl = h

cost = 0

p.sort()
q.sort()

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

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

Submission status: Runtime Error

Solution code:
# import time


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

wl = w
hl = h

cost = 0

p.sort()
q.sort()

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

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

# print time.time() - start

Submission status: Runtime Error

Solution code:
import sys
_=sys.maxint

def build_graph(W, H, p, q):
    vetex = W * H
    graph = [[_] * vetex ] * vetex
    for i in range(W):
        for j in range(H):
            x = i*W + j
            if i+1 < W:
                graph[x][x+W] = p[i]
            if j+1 < H:
                graph[x][x+1] = q[j]
    return graph

W, H = map(int, raw_input().split(' '))
p = [0] * W
q = [0] * H
for i in xrange(W):
    p[i] = int(raw_input())
for j in xrange(H):
    q[j] = int(raw_input())
W+=1
H+=1
n = W*H
g = build_graph(W,H,p,q)

def prim(graph,n):  
    dis=[0]*n  
    pre=[0]*n  
    flag=[False]*n  
    flag[0]=True  
    k=0  
    for i in range(n):  
        dis[i]=graph[k][i]  
    for j in range(n-1):  
        mini=_  
        for i in range(n):  
            if mini>dis[i] and not flag[i]:  
                mini=dis[i]  
                k=i  
        if k==0:#不连通  
            return  
        flag[k]=True  
        for i in range(n):  
            if dis[i]>graph[k][i] and not flag[i]:  
                dis[i]=graph[k][i]  
                pre[i]=k  
    return dis,pre  

dis, pre = prim(g, n)
print sum(dis[1:])

Submission status: Runtime Error

Solution code:
_=float('inf')

def build_graph(W, H, p, q):
    vetex = W * H
    graph = [[_] * vetex ] * vetex
    for i in range(W):
        for j in range(H):
            x = i*W + j
            if i+1 < W:
                graph[x][x+W] = p[i]
            if j+1 < H:
                graph[x][x+1] = q[j]
    return graph

W, H = map(int, raw_input().split(' '))
p = [0] * W
q = [0] * H
for i in xrange(W):
    p[i] = int(raw_input())
for j in xrange(H):
    q[j] = int(raw_input())
W+=1
H+=1
n = W*H
g = build_graph(W,H,p,q)

def prim(graph,n):  
    dis=[0]*n  
    pre=[0]*n  
    flag=[False]*n  
    flag[0]=True  
    k=0  
    for i in range(n):  
        dis[i]=graph[k][i]  
    for j in range(n-1):  
        mini=_  
        for i in range(n):  
            if mini>dis[i] and not flag[i]:  
                mini=dis[i]  
                k=i  
        if k==0:#不连通  
            return  
        flag[k]=True  
        for i in range(n):  
            if dis[i]>graph[k][i] and not flag[i]:  
                dis[i]=graph[k][i]  
                pre[i]=k  
    return dis,pre  

dis, pre = prim(g, n)
print sum(dis[1:])

Submission status: Runtime Error

Solution code:
def cost(x, y, a):
    if x[0] == y[0] and abs(x[1]-y[1])==1:
        if x[1] > y[1]:
            return a[1][y[i]]
        else:
            return a[1][x[i]]
    elif x[1] == y[1] and abs(x[0]-y[0])==1:
        if x[0] > y[0]:
            return a[0][y[i]]
        else:
            return a[0][x[i]]

W = 2 
H = 2

a = [[0 for i in range(W)] for j in range(H)]

for i in range(W):
    for j in range(H):
        a[i][j] = 1#input()

a = [[3,5], [2,7]]

z = list(itertools.product([0, 1, 2], repeat=2))

print(29)

Submission status: Runtime Error

Solution code:
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
# for i in xrange(h):
i = 0
while i < h:
    # for j in xrange(k,w):
        j = k
        if q[i] > p[j]:
            c += ac[j]
            i += 1
            # break
        else:
            c +=acq[i]
            k +=1
        # c += q[i]
print c

Submission status: Runtime Error

Solution code:
neighbor = lambda c, w, h: filter(
    lambda b: 0 <= b[0] <= w and 0 <= b[1] <= h,
    [
        (c[0]-1, c[1]),
        (c[0]+1, c[1]),
        (c[0], c[1]-1),
        (c[0], c[1]+1)
    ]
)

def q_c():
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append(int(raw_input()))
for j in xrange(H):
    q.append(int(raw_input()))

has = [[False for i in xrange(H+1)] for j in xrange(W+1)]
has[0][0] = True
Next = [(1, 0), (0, 1)]

cost = 0
for i in xrange(W*H+W+H):
    Min = 100000005
    choose = None
    Next.sort(key=lambda a: min(p[a[0]-1] if a[0] > 0 else 100000005, q[a[1]-1] if a[1] > 0 else 100000005))
    choose = Next[-1]
    Min = min(p[choose[0]-1] if choose[0] > 0 else 100000005, q[choose[1]-1] if choose[1] > 0 else 100000005)
    # for each in Next:
    #     if each[0] > 0:
    #         if p[each[0]-1] < Min:
    #             choose = each
    #             Min = p[each[0]-1]
    #     if each[1] > 0:
    #         if q[each[1]-1] < Min:
    #             choose = each
    #             Min = q[each[1]-1]
    has[choose[0]][choose[1]] = True
    Next = Next[:-1]
    cost += Min
    for every in neighbor(choose, W, H):
        # print every
        if not has[every[0]][every[1]] and every not in Next:
            Next.append(every)
print cost