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

N=int(input())
A=list(map(int,input().split()))
from collections import deque
import bisect
x,y,z=[],[],[]
for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])

a=x+y
a.sort()
mae=[sum(a[N:2*N])]
line=N-1
used=set()
for i in range(N-1,-1,-1):
    while line in used:
        line-=1
    idx=bisect.bisect_left(a,y[i])
    while idx in used:
        idx+=1
    used|={idx,}
    if line<idx:
        mae.append(mae[-1]-a[idx]+a[line])
        line-=1
    elif line==idx:
        mae.append(mae[-1])
        line-=1
    else:
        mae.append(mae[-1])

b=y+z
b.sort()
ushiro=[-1*sum(b[0:N])]
line=N
used=set()
for i in range(N):
    while line in used:
        line+=1
    idx=bisect.bisect_left(b,y[i])
    while idx in used:
        idx+=1
    used|={idx,}
    if idx<line:
        ushiro.append(ushiro[-1]+b[idx]-b[line])
        line+=1
    elif idx==line:
        ushiro.append(ushiro[-1])
        line+=1
    else:
        ushiro.append(ushiro[-1])
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
dataX=[]
dataY=[]
mae=dict()
ushiro=dict()
N=int(input())
A=list(map(int,input().split()))
X=A[0:N]
Y=A[N:2*N]
Z=A[2*N:3*N]
for i in range(N):
    heappush(dataX,X[i])
    heappush(dataY,-1*Z[i])
mae[0]=sum(X)
ushiro[0]=-1*sum(Z)
for i in range(1,N+1):
    mae[i]=mae[i-1]+Y[i-1]
    heappush(dataX,Y[i-1])
    mae[i]-=heappop(dataX)
    ushiro[i]=ushiro[i-1]-Y[N-i]
    heappush(dataY,-1*Y[N-i])
    ushiro[i]-=heappop(dataY)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from itertools import product

N = I()
D = III()

if N>=24:
    print(0)
elif 0 in D:
    print(0)
else:
    a = list(product([0,1],repeat=N))
    ans = 0
    for a0 in a:
        l = [False]*24
        flag = False
        for i in range(N):
            if a0[i]==0:
                if l[D[i]]:
                    flag = True
                    break
                else:
                    l[D[i]] = True
            else:
                if l[24-D[i]]:
                    flag = True
                    break
                else:
                    l[24-D[i]] = True
        if flag:
            continue
        before = 0
        val = 13
        for i in range(24):
            if l[i]:
                temp = min(i-before, 24-i+before)
                before = i
                if temp<val:
                    val = temp
        temp = min(before,24-before)
        if temp<val:
            val = temp
        if val>ans:
            ans = val
    print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from itertools import product

N = I()
D = III()

if 0 in D:
    print(0)
elif N>=24:
    print(0)
elif N==23:
    D.sort()
    for i in range(N):
        if D[i]!=i//2+1:
            print(0)
            exit()
    print(1)
else:
    a = list(product([0,1],repeat=N))
    ans = 0
    for a0 in a:
        l = [False]*24
        flag = False
        for i in range(N):
            if a0[i]==0:
                if l[D[i]]:
                    flag = True
                    break
                else:
                    l[D[i]] = True
            else:
                if l[24-D[i]]:
                    flag = True
                    break
                else:
                    l[24-D[i]] = True
        if flag:
            continue
        before = 0
        val = 13
        for i in range(24):
            if l[i]:
                temp = min(i-before, 24-i+before)
                before = i
                if temp<val:
                    val = temp
        temp = min(before,24-before)
        if temp<val:
            val = temp
        if val>ans:
            ans = val
    print(ans)
### BUGGY CODE ###

from itertools import *
from math import *

D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
seq = list(range(D))
x = list(permutations(seq, D))
#print(x)
ans = float("inf")
G2=G
for cand in x:
    cnt = 0
    G=G2
    for ind in cand:
        probpoint = (ind + 1) * 100
        if G<=0:
            break
        if G <= probpoint * (probs[ind][0] - 1):
            cnt = cnt + ceil(G / probpoint)
            G=G-probpoint*ceil(G / probpoint)
        else:
            cnt=cnt+probs[ind][0]
            G=G-(probpoint * probs[ind][0]+probs[ind][1])
    ans=min(ans,cnt)
print(ans)




### FIXED CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x=[]
for i in range(0,D+1):
    l=combinations(seq,i)
    for j in l:
        x.append(j)
x=tuple(x)
#print(x)
infty=100000
#print(x)
ans = infty
for cand in x:
    cnt = 0
    G=G2
    l=[0]*D
    for ind in cand:
        probpoint = (ind + 1) * 100
        G=G-(probpoint * probs[ind][0]+probs[ind][1])
        cnt = cnt + probs[ind][0]
        l[ind]=1
    #print(l,G,cnt)
    for i in range(D-1,-1,-1):
        if G<=0:
            break
        elif l[i]==0:
            probpoint = (i + 1) * 100
            num=ceil(G/probpoint)
            if num<probs[i][0]:
                G=G-num*probpoint
                cnt=cnt+num
            #print(cnt)
            break
    if G<=0:
        ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * n
d = [0] * (2 * n - 1)
for i in range(n - 1):
    c[i] = b[i] ^ b[i + 1]
    d[i] = a[i] ^ a[i + 1]
c[n - 1] = b[0] ^ b[-1]
d[n - 1] = a[0] ^ a[-1]
for i in range(n - 1):
    d[n + i] = d[i]
t = [0] * (n + 1)
t[0] = -1
j = -1
for i in range(n):
    while j >= 0 and c[i] != c[j]:
        j = t[j]
    j += 1
    t[i + 1] = j
m = 0
ans = []
while m < n:
    for i in range(n):
        if c[i] != d[m + i]:
            m += i - t[i]
            if i > 0:
                i = t[i]
            break
    else:
        ans.append(m)
        m = m + n - t[n]
        i = t[n]
for k in ans:
    print(k, a[k] ^ b[0])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * n
d = [0] * (2 * n - 1)
for i in range(n - 1):
    c[i] = b[i] ^ b[i + 1]
    d[i] = a[i] ^ a[i + 1]
c[n - 1] = b[0] ^ b[-1]
d[n - 1] = a[0] ^ a[-1]
for i in range(n - 1):
    d[n + i] = d[i]
t = [0] * (n + 1)
t[0] = -1
j = -1
for i in range(n):
    while j >= 0 and c[i] != c[j]:
        j = t[j]
    j += 1
    t[i + 1] = j
m = 0
i = 0
ans = []
while m < n:
    if c[i] == d[m + i]:
        i += 1
        if i == n:
            ans.append(m)
            m += i - t[i]
            i = t[i]
    else:
        m += i - t[i]
        if i > 0:
            i = t[i]
for k in ans:
    print(k, a[k] ^ b[0])
### BUGGY CODE ###

n = int(input())
a = 0
for i in range(1, n+1):
    if i % (i**0.5) == 0:
        if i > a:
            a = i
print(a)

### FIXED CODE ###

n = int(input())
for i in reversed(range(1, n+1)):
    if i % (i**0.5) == 0:
        print(i)
        exit()
### BUGGY CODE ###

def right(a,n):
    sw = [0]*(n+1)
    for x,y in enumerate(a):
        x_min = max(0,x-y)
        x_max = min(n,x+y+1)
        sw[x_min] += 1
        sw[x_max] -= 1
    s = 0
    for i in range(n):
        s += sw[i]
        a[i] = s
    return a

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(min(k,50)):
    a = right(a,n)
a = [str(n) for n in a]
print(" ".join(a))

### FIXED CODE ###

def right(a,n):
    sw = [0]*(n+1)
    for x,y in enumerate(a):
        x_min = max(0,x-y)
        x_max = min(n,x+y+1)
        sw[x_min] += 1
        sw[x_max] -= 1
    s = 0
    for i in range(n):
        s += sw[i]
        a[i] = s
    return a

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(min(k,50)):
    a = right(a,n)
a = [str(n) for n in a]
print(" ".join(a))
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
cnt_list = []
b = set(a)
for s in b:
    cnt_list.append(a.count(s))
cnt_list = sorted(cnt_list)

print(sum(cnt_list[:len(cnt_list) - k]) if len(cnt_list) - k > 0 else 0)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt_list = [0]*(n+1)
for i in range(n):
    cnt_list[a[i]] += 1
cnt_list.sort()
print(sum(cnt_list[:len(cnt_list) - k]))
### BUGGY CODE ###

import copy
N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1

A = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
A[X-1][Y-1] = 1
for t in range(N):
    if t == 0:
        continue
    sum = 0
    for u in range(N):
        sum = sum + A[u].count(t)

    print(sum)




### FIXED CODE ###


N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1
ans = [0] * (N)
A = [[] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        path = min(abs(x- i) +1 +abs(y-i-j),j)
        ans[path] += 1
for _ in range(len(ans)):
    if _ == 0:
        continue
    print(ans[_])
### BUGGY CODE ###

N = int(input())
str_lis = []
for i in range(N):
  A = str(input())
  a = []
  for i in range(len(A)):
    a.append(ord(A[i]))
  str_lis.append(a)

max_num = 0
max_str = []
for i in str_lis:
  if str_lis.count(i) > max_num and not i in max_str:
    max_num = str_lis.count(i)
    max_str = []
    max_str.append(i)
  elif str_lis.count(i) == max_num and not i in max_str:
    max_num = str_lis.count(i)
    max_str.append(i)
    
new_max_str = sorted(max_str)
 
for i in new_max_str:
  for j in range(len(i)):
    i[j] = chr(i[j])

for i in new_max_str:
  print(''.join(i))

### FIXED CODE ###

from collections import Counter

N = int(input())

str_lis = [str(input()) for i in range(N)]
c = Counter(str_lis)
a = c.most_common()
num = a[0][1]
b = []
for i in a:
  if i[1] == num:
    b.append(i[0])
    num = i[1]
  else:
    break
    
new_b = sorted(b)
for i in new_b:
  print(i)
### BUGGY CODE ###

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

count = 0
for i in range(1, N + 1):
	for j in range(1, i + 1):
		if not P[i - 1] <= P[j - 1]:
			break
		elif i == j:
			count += 1

print(count)

### FIXED CODE ###

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

max = P[0]
count = 1
for i in range(1, N):
	if max >= P[i]:
		max = P[i]
		count += 1

print(count)
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = [1]*(N+1)
for i in range(N):
    PP[i+1] = PP[i]*2 % MOD
L = [1]*(N+1)

for i in range(N, -1, -1):

    g = G[i]
    if not g:
        Q[i] = deque()
        continue

    # 子ノードのdequeを集める
    g.sort(key=L.__getitem__, reverse=1)
    k = len(g)
    e = [PP[k] - k, k, 0]

    g0 = g[0]
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    L[i] = L[g0] + 1
    R = Q[g0]
    for j in g[1:]:
        S = Q[j]

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
    Q[i] = R
ans = PP[N]
for (a0, a1, a2), c in zip(Q[0], C[1:]):
    ans += PP[N+1-c] * a1 % MOD
print(ans % MOD)

### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

ans_sum = 0
for i in range(n):
	ans_sum += a[i] * sum(a[i+1:])
	
print(ans_sum%(10**9+7))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

S = sum(a) % mod
ans_sum = 0
for i in range(n-1):
	S -= a[i]
	ans_sum += a[i] * S
	
print(ans_sum%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s_max = 0
max_i=0
ret = 0
s_list = [sum(p[i:i+k]) for i in range(n-k+1)]
s_max=max(s_list)
print(k/2+s_max/2)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
max_i=0
ret = 0
p_s=sum(p[0:k])
s_max=p_s
for i in range(n-k):
  p_s=p_s-p[i]+p[i+k]
  if s_max<p_s:
    s_max=p_s

print(s_max/2+k/2)
### BUGGY CODE ###

count = int(input())
list = [int(x) for x in input().split()]
b = 1
for a in list:
    b *= a

threshold = int(10 ** 18)

if b > threshold:
    print('-1')
else:
    print(b)

### FIXED CODE ###

def main ():
  count = int(input())
  c = list(map(int,input().split()))

  if 0 in c:
    print(0)
    return

  result = 1
  for a in c:
    result *= a
    if result > 1000000000000000000:
      print(-1)
      return

  print(result)

main()
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
p_seq = np.array(list(map(int, input().split())))
print(max(sum((p_seq[i:i+k] + 1) / 2) for i in range(n - k + 1)))


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
p_seq = np.array(list(map(int, input().split())))
e_seq = (p_seq + 1) / 2
s_seq = [0]
for e in e_seq:
    s_seq.append(s_seq[-1] + e)
print(max(s_seq[i + k] - s_seq[i] for i in range(n - k + 1)))
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):return (int(x)%kk,int(y)%kk)
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
            w[i][j]+=w[i-1][j]

    def pos(i,j):
        a=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
        b=((0,max(j-k,0),-2),(max(j-k,0),j,-1),(j,min(j+k,kk),0),(min(j+k,kk),kk,1))
        a=[(i,j,l) for i,j,l in a if i!=j]
        b=[(i,j,l) for i,j,l in b if i!=j]
        ret=[]
        for i,j,l in a:
            for x,y,z in b:
                if (l+z)%2==0:
                    ret.append((i,x,j,y))
        return ret

    def calc(i,j):
        ret=0
        for tx1,ty1,tx2,ty2 in pos(i,j):
            ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
        for tx1,ty1,tx2,ty2 in pos((i+k)%kk,j):
            ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
        return ret

    ans=0
    for i in range(kk):
        for j in range(kk):
            ans=max(ans,calc(i,j))
    print(ans)
main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
for _ in range(M):
  for i in range(N):
    if A[i] == max(A):
      A[i] = A[i]/2
      break

  
for i in range(N):
  A[i] = int(A[i])

print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
for i in range(N):
  A[i] = -A[i]
  
heapq.heapify(A)
 
for _ in range(M): 
    hoge = -heapq.heappop(A)
    hoge = hoge // 2
    heapq.heappush(A, -hoge)
 
print(-sum(A))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
k = []
j = 0
na= 0
c = 0
if sum(a)<sum(b):
    print(-1)
else:
    for i in range(n):
        if a[i]<b[i]:
            na +=b[i]-a[i]
            c+=1
        elif a[i] > b[i]:
            k.append(a[i]-b[i])
        k.sort()
    while na > 0 and k:
        na -=k[-1]
        k.pop(-1)
        c +=1
    print(c)

### FIXED CODE ###

import sys
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())
a=list(mii())
b=list(mii())
k = []
j = 0
na= 0
c = 0
for i in range(n):
    if a[i]<b[i]:
        na +=b[i]-a[i]
        c+=1
    elif a[i] > b[i]:
        k.append(a[i]-b[i])
k.sort()
while na > 0 and k:
    na -=k[-1]
    k.pop(-1)
    c +=1
if na > 0:print(-1)
else:print(c)
### BUGGY CODE ###

N, M = map(int, input().split())

l, r = map(int, input().split())
lis = [i for i in range(l, r+1)]

for i in range(M-1):
    l, r = map(int, input().split())
    tmp_lis = [i for i in range(l, r+1)]
    lis = set(lis) & set(tmp_lis)

lis = [i for i in lis if i <= N]
print(len(lis))


### FIXED CODE ###

N, M = map(int, input().split())

min, max = map(int, input().split())

for i in range(M-1):
    l, r = map(int, input().split())
    if min < l:
        min = l
    if max > r:
        max = r



lis = [i for i in range(min, max+1)]
print(len(lis))
### BUGGY CODE ###

import queue
import sys
input = sys.stdin.readline

def main():
    h,w = map(int,input().split())
    q = queue.Queue()
    A = ["" for i in range(h)]
    for i in range(h):
        b = input()
        A[i] = b
    #    print(b)
        for j in range(w):
            if b[j]=="#": q.put([i,j,0])
    #print(A)
    while not q.empty():
        a,b,c = q.get()
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=b+y<h and 0<=a+x<w and A[b+y][a+x] == ".":
                #print(b+y,a+x)
                q.put([b+y,a+x,c+1])
                l = list(A[b+y])
                l[a+x] = "#"
                A[b+y] = "".join(l)
        if q.empty():
            print(c)
            break
    #print(A)
if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np
def main():
    h,w = map(int, input().split())
    mat = []
    for i in range(h):
        b = input()
        mat.append([0 if j=="#" else h+w for j in b])
    arr = np.array(mat)

    for i in range(w-1):
        arr[:,i+1] = np.minimum(arr[:,i]+1,arr[:,i+1])
        #print(arr)

    for i in range(w-1,0,-1):
        arr[:,i-1] = np.minimum(arr[:,i]+1,arr[:,i-1])
        #print(arr)

    for i in range(h-1):
        arr[i+1,:] = np.minimum(arr[i,:]+1,arr[i+1,:])
        #print(arr)

    for i in range(h-1,0,-1):
        arr[i-1,:] = np.minimum(arr[i,:]+1, arr[i-1,:])
        #print(arr)
    print(np.max(arr))


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

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
    print(max(a[:i] + a[i+1:]))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

a_r = sorted(a, reverse=True)
for i in range(n):
    if a[i] == a_r[0]:
        print(a_r[1])
    else:
        print(a_r[0])
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
num = (n // 2) - 1

for i in range(n):
    l = x[:]
    l.pop(i)
    l.sort(reverse=True)
    print(l[num])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x[:])

for i in range(n):
    if x[i] < y[n//2]:
        print(y[n//2])
    else:
        print(y[n//2 - 1])
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  for k in range(B):
    if card_list[k] >= C:
      break
    else:
      card_list[k] = C
  card_list.sort()
      
print(sum(card_list))

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)