Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  friend=[[]for _ in range(n)]
  block=[[]for _ in range(n)]
  for a,b in ab:
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
  for c,d in cd:
    block[c-1].append(d-1)
    block[d-1].append(c-1)
  # 友達連結内でかつ友達でもブロックでもない。
  # 友達連結グループわけ
  ans=[0]*n
  seen=[0]*n
  for t in range(n):
    if seen[t]==1:
      continue
    member=[]
    todo=[t]
    seen[t]=1
    while todo:
      t=todo.pop()
      member.append(t)
      f=friend[t]
      for fi in f:
        if seen[fi]==0:
          todo.append(fi)
          seen[fi]=1
    mn=len(member)
    for m in member:
      ans[m]=mn-len([mi for mi in block[m] if mi in member])-len(friend[m])-1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  gf=[[]for _ in range(n)]
  for a,b in ab:
    gf[a-1].append(b-1)
    gf[b-1].append(a-1)
  gb=[[]for _ in range(n)]
  for c,d in cd:
    gb[c-1].append(d-1)
    gb[d-1].append(c-1)
  seen=[0]*n
  ans=[0]*n
  for i in range(n):
    c=set([i])
    if seen[i]==0:
      todo=[i]
      while todo:
        e=todo.pop()
        l=gf[e]
        for li in l:
          if seen[li]==0:
            todo.append(li)
            seen[li]=1
            c.add(li)
      base=len(c)-1
      for ci in c:
        ans[ci]=base
        for fb in gb[ci]+gf[ci]:
          if fb in c:
            ans[ci]-=1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys

a = []
for l in sys.stdin:
    if l == '\n':
        break
    else :
        a.append(l)

target = a[int(a[0])]
num = 0
for i in range(1, len(a) - 1):
    for j in range(i + 1, len(a)):
        flag = False
        for s in range(0, len(a[i]) - 1):
            if a[i].count(a[i][s]) == a[j].count(a[i][s]):
                flag = True
            else:
                flag = False
                break
        if flag:
            num = num + 1
print(num)

### FIXED CODE ###

import sys
import collections

n=int(input())
a=[''.join(sorted(input())) for _ in range(n)]

ans = 0
for v in collections.Counter(a).values():
    if v != 1:
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

for i in range(1,1000000):
    S="7"*i
    #print(S)
    S=int(S)
    if S%999983==0:
        print(S,i)

### FIXED CODE ###

K=int(input())


if K%2==0 or K%5==0:
    print(-1)
    exit()
elif K==7 or K==1:
    print(1)
else:
    M=7%K
    B=7%K
    for i in range(10**7):
        A=((B*10)%K)
        M+=A
        M%=K
        if M==0:
            print(i+2)
            exit()
        B=A+0
        #print(M,B,i)
### BUGGY CODE ###

s = input()
n = len(s)
flg=1
ans=0
while flg>0:
  flg=0
  for i in range(len(s)-1):
    if s[i]!=s[i+1]:
      s = s[:i]+s[i+2:]
      flg=1
      ans+=2
      break
print(ans)

### FIXED CODE ###

s = input()
c1,c2=s.count('0'),s.count('1'),
print(min(c1,c2)*2)
### BUGGY CODE ###

a, b, n = map(int, input().split())
c_0 = 0
m = min(n, b) + 1
for x in range(1, m):
  if x % b == 0:
    c = 0
  else:
    c = int(a * x / b)
    if c >= c_0:
      c_0 = c
print(c_0)

### FIXED CODE ###

a, b, n = map(int, input().split())
c_0 = 0
m = min(n, b-1)
x = int(a * m / b)
print(x)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
r, g, b, n = map(int, input().split())
cnt = 0
for i in range(int(n/r)+1):
    for j in range(int(n/g)+1):
        tmp = r*i + g*j
        if tmp > n:
            break
        else:
            tmp = n - tmp 
        if tmp%b == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
cnt = 0
for i in range(0, n+1, r):
    for j in range(0, n+1, g):
        tmp = n - (i+j)
        if tmp < 0:
            break
        if tmp%b == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

#inport
import sys
import numpy as np

#input
N,M = map(int, sys.stdin.readline().split())
P = [list(map(int, sys.stdin.readline().split())) for i in range(M)]

#shori
##初期化
P = np.array(P)     
ans = np.zeros((N,2))
tmp_latest = np.zeros(1)
tmp_latest_tmp = np.zeros(1)
tmp_latest[0] = 1
pos_latest = 0
num_latest = 1
ans[0][1] = 1 #部屋1をてがかりありに
flg_pos = 1
flg_fale = 0
num_crew = 1
num_left_room = N-1
left_room = np.zeros(N)

for i in range(N):
    ans[i][0] = i + 1

while num_crew < N:
    if flg_pos == 0:
        flg_fale = 1
        break

    flg_pos = 0
    for i in range(num_latest):
        tmp_room_num = tmp_latest[i]
        tmp_root = P[np.any( P == int(tmp_room_num), axis = 1)]
        root_loop_n = int(np.size(tmp_root)/2)
        for j in range(root_loop_n):
            if tmp_root[j][0]==tmp_latest[i]:
                if(ans[tmp_root[j][1]-1][1]==0):
                    tmp_latest_tmp = np.insert(tmp_latest_tmp, 0, tmp_root[j][1])
                    ans[tmp_root[j][1]-1][1] = tmp_latest[i]
                    num_crew = num_crew + 1
                    flg_pos = 1
            elif tmp_root[j][1]==tmp_latest[i]:
                if(ans[tmp_root[j][0]-1][1]==0):
                    tmp_latest_tmp = np.insert(tmp_latest_tmp, 0, tmp_root[j][0])
                    ans[tmp_root[j][0]-1][1] = tmp_latest[i]
                    num_crew = num_crew + 1
                    flg_pos = 1               
        P = np.delete(P, np.where(P == int(tmp_room_num))[0], axis = 0)

    #Nループ終了時にtmp_latestを更新
    tmp_latest = np.insert(tmp_latest, num_latest, tmp_latest_tmp)
    for j in range(num_latest):
        tmp_latest = np.delete(tmp_latest,0)
    num_latest = np.size(tmp_latest)
    tmp_latest = np.delete(tmp_latest,num_latest-1)
    num_latest = np.size(tmp_latest)
    tmp_latest_tmp = np.zeros(1)

    
if flg_fale == 0:
    print('Yes')
    for i in range(N-1):
        print(int(ans[i+1][1]))
else:
    print('No')


### FIXED CODE ###

#inport
import sys
import numpy as np
from collections import deque


#input
N,M = [int(x) for x in sys.stdin.readline().split()]
g = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    g[a].append(b)
    g[b].append(a)



quetmp = deque([1])
d = [None] * (N+1)
d[1] = 0
num_crew = 1
while quetmp:
    v = quetmp.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v
            quetmp.append(i)
            num_crew = num_crew + 1

if num_crew == N:
    print('Yes')
    for i in range(N-1):
        print(d[i+2])
else:
    print('No')
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
As = list(map(int, input().split()))

def f(x):
    # サイズxで切る
    cnt = 0
    for a in As:
        # 斬らなければイケない本数
        cnt += int(np.ceil(a/x))-1
        if cnt > k:
            return False
    # 斬らなければいけない本数がk本以下
    return cnt <= k

l = 10**-2
r = 10**9
while r-l > 10**-1:
    m = (l*r)**0.5
    if f(m):
        r = m
    else:
        l = m
print(int(np.ceil(l)))

### FIXED CODE ###

n,k = map(int, input().split())
As = list(map(int, input().split()))

def f(x):
    # サイズxで切る
    cnt = 0
    for a in As:
        # 斬らなければイケない本数
        cnt += int((a-0.01)/x)
        if cnt > k:
            return False
    # 斬らなければいけない本数がk本以下
    return cnt <= k

l = 10**-2
r = 10**9
while r-l > 10**-1:
    m = (l*r)**0.5
    if f(m):
        r = m
    else:
        l = m
print(int(l)+1)
### BUGGY CODE ###

N = int(input())
A = [int(k) for k in input().split()]

result = True

# for char in A:
#     if(A.count(char) != 1):
#         result = False
#         break
for i in range(N):
    for j in range(i+1, N):
        # print("A[i]= "+str(A[i])+", A[j]= "+str(A[j]))
        if A[i] == A[j]:
            result = False

if (result == True):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

N = int(input())
A = [int(k) for k in input().split()]

result = True

# for char in A:
#     if(A.count(char) != 1):
#         result = False
#         break
# for i in range(N):
#     for j in range(i+1, N):
#         # print("A[i]= "+str(A[i])+", A[j]= "+str(A[j]))
#         if A[i] == A[j]:
#             result = False
A.sort()

for i in range(N-1):
    if (A[i] == A[i+1]):
        result = False
        break

if (result == True):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

mod=1000000007
s=input()
l=len(s)
DP=[[0]*13 for _ in range(l+1)]
DP[0][0]=1
for i in range(1,l+1):
    d=s[-i]
    tmp=(10**(i-1))%13
    if d=='?':
        for j in range(10):
            for k in range(13):
                DP[i][(k+tmp*j)%13]+=DP[i-1][k]
                DP[i][(k+tmp*j)%13]%=mod
    else:
        d=int(d)
        for k in range(13):
            DP[i][(k+tmp*d)%13]+=DP[i-1][k]
            DP[i][(k+tmp*d)%13]%=mod
print(DP[-1][5])

### FIXED CODE ###

def main():
    mod=1000000007
    s=input()
    l=len(s)
    DP=[[0]*13 for _ in range(l+1)]
    DP[0][0]=1
    for i in range(1,l+1):
        d=s[-i]
        tmp=pow(10,i-1,13)
        if d=='?':
            for j in range(10):
                for k in range(13):
                    m=(k+tmp*j)%13
                    DP[i][m]+=DP[i-1][k]
                    if DP[i][m]>=mod:
                        DP[i][m]-=mod
        else:
            d=int(d)
            for k in range(13):
                m=(k+tmp*d)%13
                DP[i][m]+=DP[i-1][k]
                if DP[i][m]>=mod:
                    DP[i][m]-=mod
    print(DP[-1][5])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    q = [(0, sh-1, sw-1)]
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    while q:
        cnt, h, w = heappop(q)
        if dist[h][w] < cnt: continue
        dist[h][w] = cnt
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    heappush(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    heappush(q, (cnt+1, nh, nw))
    return -1

print(main())


### FIXED CODE ###

from collections import deque
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, sh-1, sw-1))
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while q:
        cnt, h, w = deque.popleft(q)
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    deque.appendleft(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    deque.append(q, (cnt+1, nh, nw))
    return -1

print(main())
### BUGGY CODE ###

N=int(input())
cnt=0
for a in range(1,N):
    for b in range(1,N):
        for c in range(1,N):
            if(a*b+c==N):
                cnt+=1    
print(cnt)

### FIXED CODE ###

N=int(input())
cnt=0
for a in range(1,N):
    for b in range(a,N):
        if(a*b<N):
            if(a==b):
                cnt+=1
            else:
                cnt+=2
        else:
            break
print(cnt)
### BUGGY CODE ###

n=int(input())

if n==1:
    print("Yes")
    print(2)
    print(1,1)
    print(1,1)
    exit()
a=1
while True:
    t=a*(a-1)//2
    if t>n:
        print("No")
        exit()
    if t==n:
        print("Yes")
        break
    a+=1
print(a)
s=set(range(1,1+n))
l=[0]*(n+1)
ans=[set()]

for i in range(a):
    ll=set()
    for j in ans[:i+1]:
        for p in s&j:
            if p not in ll:
                ll.add(p)
                if l[p]==1:
                    s.remove(p)
                else:
                    l[p]+=1
                break

    for p in s:
        if len(ll)>=n*2//a:
            break
        else:
            if l[p]==0:
                ll.add(p)
                l[p]+=1

    ans.append(ll)
    q=[n*2//a]+list(ll)
    print(*q)










### FIXED CODE ###

def main():
    n=int(input())
    m=int((2*n)**0.5)
    if m*(m+1)==n*2:
        print("Yes")
        m+=1
        print(m)
    else:
        print("No")
        exit()
    
    ans=[[m-1] for i in range(m)]
    c=1
    for i in range(m):
        for j in range(i+1,m):
            ans[i].append(c)
            ans[j].append(c)
            c+=1
    for i in ans:
        print(*i)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

a = int(input()) 
b = [int(input()) for i in range(a)] 
for i in range(a):
  d=b[i]
  b.pop(i)
  print(max(b))
  b.insert(i,d)

### FIXED CODE ###

a = int(input()) 
b = [int(input()) for i in range(a)] 
 
m=max(b)
sorted(b)
s=sorted(b)[-2]
for i in range(a):
  if m>b[i]:
    print(m)
  else:
    print(s)
### BUGGY CODE ###

n, *p_n = map(int, open(0).read().split())

count = 0
for i in range(n):
    for j in range(i):
        if p_n[i] > p_n[j]:
            break
        if j == i-1:
            count += 1
            

print(count + 1)


### FIXED CODE ###

n, *p_n = map(int, open(0).read().split())

count = 0
p_n_min = p_n[0]
for i in range(n):
    p_n_min = min(p_n_min,p_n[i])
    if p_n_min == p_n[i]:
        count += 1
print(count)
### BUGGY CODE ###

x,y = map(int,input().split())
ans = -1
i = 1

if x == y:
    ans = -1
else:
    while True:
        a = (x*i) % y
        if a != 0:
            ans = x*i
            break
        else:
            i += 1

print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
ans = -1
i = 1

while True:
    a = (x*i) % y
    if a != 0:
        ans = x*i
        break
    else:
        ans = -1
        break

print(ans)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse = True)

flg = 0
heap = []

for i in range(N):
	heapq.heappush(heap, [- A[i] * F[i], F[i]])
	
for i in range(K):
	score, tmp_F = heapq.heappop(heap)
	if score != 0:
		score += tmp_F
		heapq.heappush(heap, [score, tmp_F])
	else:
		flg = 1
		break
		
if flg:
	print(0)
else:
	ret = heapq.heappop(heap)
	print(-1 * ret[0])	

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

ng = -1
ok = 10 ** 12

while ok - ng > 1:
	mid = (ok + ng) // 2
	ctr = 0
	for i in range(N):
		ctr += max(0, A[i] - mid // F[i])
	if ctr <= K:
		ok = mid
	else:
		ng = mid

print(ok)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

for i in range(len(A)):
    print(A.index(i+1)+1, end='')
    if i == len(A) - 1:
        print()
    else:
        print(' ', end='')

### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))

ans = []

for i, j in enumerate(A):
    ans.append((j, i+1))

ans.sort()

for i, j in ans:
    print(j, end='')
    if i == len(ans):
        print()
    else:
        print(' ', end='')
### BUGGY CODE ###

import itertools
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges
n,m,r = map(int,input().split())
a = list(map(int,input().split()))
b = [list(map(int,input().split())) for l in range(m)]
d = [[float("inf")]*n for i in range(n)]
for i in range(m):
  d[b[i][0]-1][b[i][1]-1] = min(b[i][2],d[b[i][0]-1][b[i][1]-1])
  d[b[i][1]-1][b[i][0]-1] = min(b[i][2],d[b[i][1]-1][b[i][0]-1])
d = Warshall_Floyd(d,n)
kumi = list(itertools.permutations(a, r))
kota = float("inf")
for i in kumi:
  ans = 0
  for j in range(1,r):
    ans += d[i[j-1]-1][i[j]-1]
  kota = min(ans,kota)
print(kota)

### FIXED CODE ###

import itertools
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges
n,m,r = map(int,input().split())
a = list(map(int,input().split()))
b = [list(map(int,input().split())) for l in range(m)]
d = [[float("inf")]*n for i in range(n)]
for i in range(m):
  d[b[i][0]-1][b[i][1]-1] = min(b[i][2],d[b[i][0]-1][b[i][1]-1])
  d[b[i][1]-1][b[i][0]-1] = min(b[i][2],d[b[i][1]-1][b[i][0]-1])
d = Warshall_Floyd(d,n)
kumi = list(itertools.permutations(a, r))
kota = float("inf")
for i in kumi:
  ans = 0
  for j in range(1,r):
    ans += d[i[j-1]-1][i[j]-1]
  kota = min(ans,kota)
print(kota)
### BUGGY CODE ###

num = int(input())
a_i = list(map(int, input().split()))
anslist = [0] * (num + 1)
for x in range(num):
    val = x + 1
    cnt = a_i.count(val)
    if cnt <= 1: anslist[val] = 0
    else: anslist[val] = cnt * (cnt - 1) // 2

ans = sum(anslist)
for x in range(num):
    val = a_i[x]
    cnt = a_i.count(val)
    if cnt <= 1: print(ans)
    else: 
        sa = (cnt - 1)
        print(ans - sa)
        

### FIXED CODE ###

import collections

num = int(input())
a_i = list(map(int, input().split()))
anslist = collections.Counter(a_i)

ans = 0
for x in anslist.values():
    ans += x * (x - 1) // 2
for x in range(num):
    val = a_i[x]
    cnt = anslist[val]
    print(ans - (cnt - 1))
### BUGGY CODE ###

N = int(input())
memo = [0]*(N+1)
for x in range(1,N+1):
    for y in range(x,N+1,x):
        memo[y] += 1
print(sum(c*m for c,m in enumerate(memo)))

### FIXED CODE ###

N = int(input())

memo = list(range(N+1))

temp = [0]*(N+1)
temp[0] = 1
temp[1] = 1

for x,c in enumerate(memo):
    if temp[x] == 0:
        for y in range(x,N+1,x):
            memo[y] *= temp[y]+1
            temp[y] = 1
        k = 2
        while x**k <= N:
            for y in range(x**k,N+1,x**k):
                temp[y] += 1
            k += 1
    memo[x] *= temp[x]+1

print(sum(memo)-1)
### BUGGY CODE ###

n = int(input())
a = [input() for i in range(n)] 
ans =1
s = [a[0]]

for i in a[1:]:
    if not i in s:
        ans += 1
        s.append(i)
    else:
        continue
print(ans)    


### FIXED CODE ###

import collections
N=int(input())
S=[]
for i in range(N):
    S.append(input())
s=collections.Counter(S)
s_key=s.keys()
print(len(s_key))
### BUGGY CODE ###

ans=10**9
N,C=map(int,input().split())
s=[list(map(int,input().split())) for i in range(C)]
t=[list(map(int,input().split())) for i in range(N)]
u=[[0]*C for i in range(3)]
for i in range(N):
    for j in range(N):
        for k in range(C):
            u[(i+j)%3][k]+=s[t[i][j]-1][k]
from itertools import permutations
for i,j,k in list(permutations(range(C),3)):
    p=u[0][i]+u[1][j]+u[2][k]
    ans=min(ans,p)
print(ans)    


### FIXED CODE ###

import numpy as np
N,C=map(int,input().split())
ans=10**9
a=np.array([0]*C)
b=np.array([0]*C)
c=np.array([0]*C)
s=[]
t=[]
for i in range(C):
    s.append(list(map(int,input().split())))
for i in range(N):
    t.append(list(map(int,input().split())))
for j in range(N):
    for i in range(N):
        if (i+j)%3==0:
            a+=np.array(s[t[i][j]-1])
        elif (i+j)%3==1:
            b+=np.array(s[t[i][j]-1])
        else:
            c+=np.array(s[t[i][j]-1])
from itertools import permutations
for i,j,k in permutations(range(C),3):
    p=a[i]+b[j]+c[k]
    ans=min(p,ans)
print(ans)
### BUGGY CODE ###

from itertools import takewhile

# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]

# 各マスについて、横方向に照らすマスの数と縦方向に照らすマスの数を求める
x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if x[i][j] == 0:
            c = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
            for k in range(j, j + c):
                if S[i][k] == '.':
                    x[i][k] = c
        if y[i][j] == 0:
            c = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
            for k in range(i, i + c):
                if S[k][j] == '.':
                    y[k][j] = c
ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)


### FIXED CODE ###

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

dp1 = [[0 for _ in range(W)] for _ in range(H)]
dp2 = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if dp1[i][j] == 0 and S[i][j] == '.':
            c = 0
            for k in range(i, H):
                if S[k][j] == '.':
                    c += 1
                else:
                    break
            for k in range(i, H):
                if S[k][j] == '.':
                    dp1[k][j] = c
                else:
                    break
for i in range(H):
    for j in range(W):
        if dp2[i][j] == 0 and S[i][j] == '.':
            c = 0
            for k in range(j, W):
                if S[i][k] == '.':
                    c += 1
                else:
                    break
            for k in range(j, W):
                if S[i][k] == '.':
                    dp2[i][k] = c
                else:
                    break

ans = max(
    dp1[i][j] + dp2[i][j] - 1
    for i in range(H)
    for j in range(W)
)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from heapq import *
from array import *

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

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

def mst_prim(adj, n):
    pred = defaultdict(lambda: -1)
    key = defaultdict(lambda: float('inf'))
    key[0] = 0
    pq = [(key[v], v) for v in range(n)]
    heapify(pq)
    in_pq = array('B', (True for _ in range(n)))
    while pq:
        _,u = heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

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

    adj = defaultdict(set)
    for x in range(w+1):
        for y in range(h+1):
            if x < w:
                adj[x+y*(w+1)].add((x+1+y*(w+1), p[x]))
                adj[x+1+y*(w+1)].add((x+y*(w+1), p[x]))
            if y < h:
                adj[x+y*(w+1)].add((x+(y+1)*(w+1), q[y]))
                adj[x+(y+1)*(w+1)].add((x+y*(w+1), q[y]))
    print(sum(mst_prim(adj, (w+1)*(h+1))[1].values()))

main()


### FIXED CODE ###

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()