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

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    A = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    dist = [[INF] * W for i in range(H)]
    que = collections.deque()

    for i, j in itertools.product(range(H), range(W)):
        if A[i][j] == '#':
            que.append((i, j))
            dist[i][j] = 0

    while que:
        cy, cx = que.popleft()
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and dist[cy][cx] + 1 < dist[ny][nx]:
                dist[ny][nx] = dist[cy][cx] + 1
                que.append((ny, nx))

    # for i in dist:
    #     print(i)

    ans = max([max(i) for i in dist])
    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    A = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    dist = [[INF] * W for i in range(H)]
    que = collections.deque()

    for i, j in itertools.product(range(H), range(W)):
        if A[i][j] == '#':
            que.append((i, j))
            dist[i][j] = 0

    while que:
        cy, cx = que.popleft()
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and dist[cy][cx] + 1 < dist[ny][nx]:
                dist[ny][nx] = dist[cy][cx] + 1
                que.append((ny, nx))

    # for i in dist:
    #     print(i)

    ans = max([max(i) for i in dist])
    print(ans)

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

F_str = input().split()
F = [int(f) for f in F_str]
N = F[0]
M = F[1]

WA_list = [0 for _ in range(N)]
AC_list = []

for i in range(M):
    S_str = input().split()
    S = [str(s) for s in S_str]
    if(S[1] == "AC"):
        AC_list.append(S[0])
        AC_list = list(set(AC_list))
    elif(not(S[0] in AC_list)):
        WA_list[int(S[0])-1] += 1
        
WA_count = 0

for item in AC_list:
    WA_count += WA_list[int(item)-1]

print(str(len(AC_list)) + " " + str(WA_count))

### FIXED CODE ###

F_str = input().split()
F = [int(f) for f in F_str]
N = F[0]
M = F[1]

WA_list = [0 for _ in range(N)]
AC_list = [0 for _ in range(N)]

for i in range(M):
    S_str = input().split()
    S = [str(s) for s in S_str]
    if(S[1] == "AC"):
        AC_list[int(S[0])-1] = 1
    elif(AC_list[int(S[0])-1] != 1):
        WA_list[int(S[0])-1] += 1

WA_count = 0
AC_count = 0

for i in range(N):
    if(AC_list[i] == 1):
        AC_count += 1
        WA_count += WA_list[i]

print(AC_count, WA_count)
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)//(1<<b)for a in f]
  v=[(a&1<<b)//(1<<b)for a in g]
  q=[[(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j])for j in range(n)]for i in range(n)]
  for i in range(n):
    if s[i]*u[i]*(sum(q[i])==0):
      for j in range(n):
        if(t[j]^1)*(n-sum(k[j]for k in q)>1):q[i][j]=u[i];break
  for j in range(n):
    if t[j]*v[j]*(sum(k[j]for k in q)==0):
      for i in range(n):
        if(s[i]^1)*(n-sum(q[i])>1):q[i][j]=v[j];break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]<<b
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
ss=[u[i]if s[i]==0 else 0 for i in range(n)]
tt=[v[i]if t[i]==0 else 0 for i in range(n)]
son=[[]for _ in range(n)]
ton=[[]for _ in range(n)]
sno=[[n-1]*64 for _ in range(n)]
tno=[[n-1]*64 for _ in range(n)]
for i in range(n):
  for j in range(n):
    ans[i][j]=u[i]&v[j]
    if s[i]==0:
      ans[i][j]|=u[i]
      ss[i]&=ans[i][j]
    else:
      ss[i]|=ans[i][j]
    if t[j]==0:
      ans[i][j]|=v[j]
      tt[j]&=ans[i][j]
    else:
      tt[j]|=ans[i][j]
    if s[i]==0 or t[i]==0:
      for k in range(64):
        if ans[i][j]&1<<k:
          if s[i]==0:sno[i][k]-=1
          if t[j]==0:tno[j][k]-=1
    if j==n-1:
      if s[i]==1:
        if ss[i]|u[i]>u[i]:print(-1);exit()
        if ss[i]!=u[i]:
          for k in range(64):
            if u[i]&1<<k:
              if (ss[i]&1<<k)==0:
                son[i].append(k)
          ss[i]=1
        else:ss[i]=0
      else:
        if ss[i]!=u[i]:print(-1);exit()
        else:ss[i]=2
    if i==n-1:
      if t[j]==1:
        if tt[j]|v[j]>v[j]:print(-1);exit()
        if tt[j]!=v[j]:
          for k in range(64):
            if v[j]&1<<k:
              if (tt[j]&1<<k)==0:
                ton[j].append(k)
          tt[j]=1
        else:tt[j]=0
      else:
        if tt[j]!=v[j]:print(-1);exit()
        else:tt[j]=2
for i in range(n):
  for k in son[i]:
    for j in range(n):
      if t[j]==0:
        if tno[j][k]>0:
          ans[i][j]|=1<<k
          tno[j][k]-=1
          break
      if j==n-1:print(-1);exit()
for j in range(n):
  for k in ton[j]:
    for i in range(n):
      if s[i]==0:
        if sno[i][k]>0:
          ans[i][j]|=1<<k
          sno[i][k]-=1
          break
      if i==n-1:print(-1);exit()
for i in range(n):
  if s[i]==0:uu=ans[i][0]
  else:uu=0
  for j in range(n):
    if s[i]==0:uu&=ans[i][j]
    else:uu|=ans[i][j]
  if uu!=u[i]:print(-1);exit()
for j in range(n):
  if t[j]==0:vv=ans[0][j]
  else:vv=0
  for i in range(n):
    if t[j]==0:vv&=ans[i][j]
    else:vv|=ans[i][j]
  if vv!=v[j]:print(-1);exit()
for i in ans:print(*i)
### BUGGY CODE ###

from collections import Counter

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

c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))

for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x

ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1

print(ans)

### FIXED CODE ###

#Ai/Aj not integer
#5
#24 11 8 3 16
#のときは、24は8,3があるからダメ　16も8があるからダメ
N=int(input())
A=[int(i) for i in input().split()]
D=set()
S=set()
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])
M=max(S)
X=[1 for i in range(M+1)]
for a in S:
    if a in D:
        X[a]=0
    for i in range(2*a,M+1,a):
        X[i]=0
ans=0
for i in range(N):
    if X[A[i]]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ct = 0
for i in range(n):
    for j in range(i, n):
        if j - i == A[i] + A[j]:
            ct += 1
print(ct)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(n):
    L = i + A[i]
    if L not in dic:
        dic[L] = 1
    else:
        dic[L] += 1
for j in range(n):
    R = j - A[j]
    if R in dic:
        ans += dic[R]
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [str(a.index(i + 1) + 1) for i in range(n)]
print(" ".join(ans))


### FIXED CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_c
n = int(input())
a = list(map(int, input().split()))
#### TLE ####
# ans = [str(a.index(i + 1) + 1) for i in range(n)]
# print(" ".join(ans))

b = [" "] * n
for i in range(n):
    b[a[i]-1] = str(i+1)

print(" ".join(b))
### BUGGY CODE ###

K,S=map(int, input().split())
count = 0
for x in range(min([K+1,S+1])):
  for y in range(min([K+1,S+1-x])):
    for z in range(min([K+1,S+1-x-y])):
      if x+y+z == S:
        count = count + 1
print(count)


### FIXED CODE ###

K,S=map(int, input().split())
count = 0
for x in range(min([K+1,S+1])):
  for y in range(min([K+1,S+1-x])):
    if S-x-y<=K:
      count = count + 1
print(count)
### BUGGY CODE ###

n = int(input())

lis = []

for k in range(1,101):
    for l in range(1,101):
        for m in range(1,101):
            lis.append(k ** 2 + l ** 2 + m ** 2 + k * l + l * m + m * k)

for p in range(1, n + 1):
    print(lis.count(p))

### FIXED CODE ###

import collections
n = int(input())

lis = []

for k in range(1,101):
    for l in range(1,101):
        for m in range(1,101):
            lis.append(k ** 2 + l ** 2 + m ** 2 + k * l + l * m + m * k)

c = collections.Counter(lis)
for p in range(1, n + 1):
    print(c[p])
### BUGGY CODE ###

a,b,x = map(int,input().split())
t = 0

for i in range(a,b+1):
    if i % x == 0:
        t += 1

print(t)

### FIXED CODE ###

a,b,x = map(int,input().split())
b = b // x + 1
a = (a - 1) // x + 1
print(b - a)
### BUGGY CODE ###

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

A.sort()
B.sort()
C.sort()
tmp = [0]*N
for i in reversed(range(N)):
    if i == N-1:
        for j in range(N):
            if C[j] > B[i]:
                tmp[i] += 1
    else:

        for j in range(N):
            if C[j] > B[i+1]:
                tmp[i] += tmp[i+1]
                break
            if C[j] > B[i]:
                tmp[i] += 1


ans = 0
for i in range(N):
    k = 0
    for j in range(k, N):
        # print(ans)
        if B[j] > A[i]:
            ans += sum(tmp[j:])
            k = j
            break


print(ans)


### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans=0
BC=[0]*N
for i in range(N):
  id = bisect.bisect_right(C,B[i])
  BC[i]=N-id
sBC=[0]*(N+1)
for i in range(1,N+1):
  sBC[i]=sBC[i-1]+BC[i-1]
for i in range(N):
  id=bisect.bisect_right(B,A[i])
  ans+=sBC[N]-sBC[id]
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = []
for i in input().split():
	a.append(int(i))
b = []
for i in input().split():
	b.append(int(i))
c = []
for i in input().split():
	c.append(int(i))

#a.reverse()
#b.reverse()
#c.reverse()

sum = []

for i in range(x):
	for j in range(y):
		for jj in range(z):
			sum.append(a[i]+b[j]+c[jj])
sum.sort()
sum.reverse()

#print(sum)
summ = 0

for i in range(k):
	print(sum[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = []
for i in input().split():
	a.append(int(i))
b = []
for i in input().split():
	b.append(int(i))
c = []
for i in input().split():
	c.append(int(i))

#a.reverse()
#b.reverse()
#c.reverse()

a_bsum = []

for i in range(x):
	for j in range(y):
			a_bsum.append(a[i]+b[j])
a_bsum.sort()
a_bsum.reverse()

a_bsum = a_bsum[0:k]

sum = []

c.sort()
c.reverse()
c = c[0:k]

for i in a_bsum:
	for j in c:
		sum.append(i+j)

sum.sort()
sum.reverse()

for i in range(k):
	print(sum[i])
### BUGGY CODE ###

a,s=map(int,input().split())
l=list(input())
for i in range(s):
  p,q=map(int,input().split())
  c=0
  for o in range(p,q):
    if l[o-1]=="A" and l[o]=="C":
      c+=1
  print(c)
    


### FIXED CODE ###

n,m=map(int,input().split())
l=list(input())
list=[0]
c=0
for i in range(len(l)-1):
  if l[i]=="A" and l[i+1]=="C":
    c+=1
    list.append(c)
  else:
    list.append(c)
for i in range(m):
  n,m=map(int,input().split())
  print(list[m-1]-list[n-1])
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = input()

cnt = []
cnt.append(Counter(s[1:])["E"])
cnt.append(Counter(s[:n])["W"])
for i in range(1, n-1):
    a = Counter(s[:i])["W"]
    b = Counter(s[i+1:])["E"]
    cnt.append(a+b)
print(min(cnt))


### FIXED CODE ###

import numpy as np

n = int(input())
s = input()
s_W = [0]
s_E = []

for i in range(n):
    if s[i] == "W":
        s_W.append(1)
        s_E.append(0)
    else:
        s_W.append(0)
        s_E.append(1)

W_l = np.cumsum(np.array(s_W))
E_l = np.cumsum(np.array(s_E))

ans = []
for j in range(n):
    num = W_l[j]-W_l[0]+E_l[-1]-E_l[j]
    ans.append(num)
print(min(ans))
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
a={i for i in range(A,B+1)}
b=set()
c=set()
u=B//C
t=B//D
for i in range(1,u+1):
  b.add(i*C)
for j in range(1,t+1):
  c.add(j*D)
print(len(a-b-c))  


### FIXED CODE ###

A,B,C,D=map(int,input().split())

def unko(x,C,D):
  import fractions
  t=int(fractions.gcd(C,D))
  t_=C*D//t
  return x-(x//C+x//D-x//t_)
print(int(unko(B,C,D)-unko(A-1,C,D)))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(10 ** 7)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 10 ** 7, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(2 * (10 ** 6))]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 2 * (10 ** 6), a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return lis[:now+1] + [item] + lis[now+1:]
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
for k in range(res):
  cut[length[0][1]] += 1
  length[0][0] = length[0][0]*cut[length[0][1]]/(cut[length[0][1]]+1)
  if length[0][0] < length[1][0]:
    length = nibun_insert(length[1:], length[0])

   
print(math.ceil(length[0][0]))



### FIXED CODE ###

import math
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return deque(lis[:now+1] + [item] + lis[now+1:])
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
length = deque(length)
for k in range(res):
  a = length.popleft()
  cut[a[1]] += 1
  a[0] = a[0]*cut[a[1]]/(cut[a[1]]+1)
  if a[0] <= length[-1][0]:
    length.append(a)
  elif a[0] >= length[0][0]:
    length.appendleft(a)
  else:
    length = nibun_insert(list(length), list(a))
  length.pop()

print(math.ceil(length.popleft()[0]))
### BUGGY CODE ###

num = input()
list = list(map(int,input().split()))
flg  = False
for i in list:
  if list.count(i) >= 2:
    flg = True
    break
print("NO") if flg else print("YES")


### FIXED CODE ###

num = input()
list = list(map(int,input().split()))
list2 = set(list) 
print("YES") if len(list) == len(list2) else print("NO")
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q = deque([(x1,y1,0,(0,0),0)])
dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[float("inf")]*w for _ in range(h)]
dist[x1][y1] = 0
while q:
    x, y, d, t, td = q.popleft()
    for xx, yy in zip(dx,dy):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if nd<=dist[nx][ny]:
            q.append((nx,ny,nd,(xx,yy),ntd))
            dist[nx][ny] = nd
if dist[x2][y2] >10**10:
    print(-1)
else:
    print(dist[x2][y2])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q0 = deque([(0,x1,y1,(0,0),0)])
q1 = deque()

dx = [0,1,0,-1]
dy = [1,0,-1,0]
# dist = [[None]*w for _ in range(h)]
dist = [None]*(w*h)
dist[x1*w+y1] = 0
# done = [[0]*w for _ in range(h)]
done = [0]*(w*h)
done[x1*w+y1] = 15

while q0 or q1:
    if not q0:
        q0 = q1
        q1 = deque()
    d, x, y, t, td = q0.popleft()
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
            q = q0
        else:
            nd = d+1
            ntd = 1
            q = q1
        if dist[nx*w+ny] is None or nd<dist[nx*w+ny]:
            q.append((nd,nx,ny,(xx,yy),ntd))
            dist[nx*w+ny] = nd
            done[nx*w+ny] = 1<<(i)
        elif nd==dist[nx*w+ny]and ((done[nx*w+ny]&1<<(i))==0):
            q.append((nd,nx,ny,(xx,yy),ntd))
            done[nx*w+ny] |= 1<<(i)
            
if dist[x2*w+y2] is None:
    print(-1)
else:
    print(dist[x2*w+y2])
### BUGGY CODE ###

import sys
import numpy as np
n = int(input())
hight = np.array([int(i) for i in input().split()])
if n == 1:
    print('Yes')
    sys.exit()

diff = np.diff(hight)
if min(diff) < -1:
    print('No')
    sys.exit()

nonzero = np.nonzero(diff == -1)[0]
if len(nonzero) > 1:
    for i,j in enumerate(nonzero):
        for k in nonzero[i+1:]:
            if k == j+1:
                print('No')
                sys.exit()
print('Yes')

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
h.reverse()
next = h[0]
import sys
for i in h[1:]:
    if i - next > 1:
        print('No')
        sys.exit()
    elif i - next == 1:
        next = i - 1
    else:
        next = i
print('Yes')
### BUGGY CODE ###

class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)
n,a,b=map(int,input().split())
lim=10**9+7
c = Combinatorics(n,lim)
ans = (2**n-1-c.binom(n,a)-c.binom(n,b))
print(ans%lim)

### FIXED CODE ###

n,a,b = map(int,input().split())
lim = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

print((pow(2,n,lim)-combination(n,a)-combination(n,b)-1) % lim)
### BUGGY CODE ###

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

max_pos = 0
max_value = sum(P[:K])
tmp_sum = max_value
for i in range(N-K):
    tmp_sum = tmp_sum - P[i] + P[i+K]
#    print(i, max_value, tmp_sum, P[i:i+K], "-", P[i], "+", P[i+K])
    if tmp_sum > max_value:
        max_value = tmp_sum
        max_pos = i + 1

#print("--------", max_pos)
total = 0
for i in range(max_pos, max_pos + K):
    total += sum(list(range(1, P[i] + 1))) / P[i]
#    print(i, total, sum(list(range(1, P[i] + 1))) / P[i])

print(total)


### FIXED CODE ###

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

max_pos = 0
max_value = sum(P[:K])
tmp_sum = max_value
for i in range(N-K):
    tmp_sum = tmp_sum - P[i] + P[i+K]
#    print(i, max_value, tmp_sum, P[i:i+K], "-", P[i], "+", P[i+K])
    if tmp_sum > max_value:
        max_value = tmp_sum
        max_pos = i + 1

#print("--------", max_pos)
total = 0
for i in range(max_pos, max_pos + K):
    total += (P[i] + 1) / 2
#    print(i, total, sum(list(range(1, P[i] + 1))) / P[i])

print(total)
### BUGGY CODE ###

def main():
    n, m = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    for _ in range(m):
        b, c = [int(i) for i in input().split()]
        for _ in range(b):
            a.append(c)
    a = sorted(a)[-n:]
    print(sum(a))


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n, m = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    
    bc = []
    for _ in range(m):
        b, c = map(int, input().split())
        bc.append((b, c))

    total = 0
    for num, v in sorted(bc, key=lambda x: -x[1]):
        total += num
        a.extend([v]*num)
        if total >= n:
            break
    print(sum(sorted(a)[-n:]))

if __name__ == '__main__':
    main()