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

from collections import deque


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while q:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))

    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10**18
mod = 10**9+7

dic = {}

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
a = list(map(int, input().split()))
j = []
for num in a:
    tmp = factorization(num)
    j.append(tmp)
    for p,x in tmp:
        if p in dic:
            dic[p] = max(dic[p],x)
        else:
            dic[p] = x
pow = {k:[k**i for i in range(v+1)] for k,v in dic.items()}
ans = 0
for i in range(n):
    preans = 1
    dicans = {k:v for k,v in dic.items()}
    for p,x in j[i]:
        dicans[p] -= x
    for k,v in dicans.items():
        preans = preans*pow[k][v]%mod
    ans = (ans+preans)%mod
print(ans)


### FIXED CODE ###

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10**18
mod = 10**9+7

dic = {}

# mod で割り算(フェルマー、逆元利用)
mod = 10**9+7

N = 10**6+1
inv_t = [0]+[1]

for i in range(2,N):
    inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

def moddiv(a, b):
    return a*inv_t[b]%mod

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
a = list(map(int, input().split()))
j = []
for num in a:
    tmp = factorization(num)
    j.append(tmp)
    for p,x in tmp:
        if p in dic:
            dic[p] = max(dic[p],x)
        else:
            dic[p] = x
gc = 1
for k,v in dic.items():
    gc*=(k**v)%mod
ans = 0
for num in a:
    ans += moddiv(gc, num)
    ans %= mod
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N // R + 1):
    for g in range(N // G + 1):
        if (N - r * R - g * G) % B == 0 and (N - r * R - g * G) >= 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N // R + 1):
    for g in range(N // G + 1):
        if (N - r * R - g * G) % B == 0 and (N - r * R - g * G) >= 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

h,w,k= map(int, input().split())
sx,sy,gx,gy= map(int, input().split())
maze= [list(input()) for i in range(h)]


# 迷路　BFS
def clear_maze(sx, sy, gx, gy):

    INF=-10**9
    distance = [[INF for i in range(w)] for j in range(h)]
    #    distance = [[None]*field_x_length]*field_y_length
    def bfs():
        # きた点と方向を格納
        d=deque()
        d.append((sx, sy))
        distance[sx][sy] =0

        while len(d):
            x, y = d.popleft()

            for i in range(0, 4):
                for j in range(1,k+1):
                    nx, ny = x + [j, 0, -j, 0][i], y + [0, j, 0, -j][i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if maze[nx][ny]=='@':
                            break
                        elif distance[nx][ny] == INF:
                            d.append((nx, ny))
                            distance[nx][ny] = distance[x][y] + 1

                    else:
                        break

        return distance[gx][gy]

    return bfs()

ans=clear_maze(sx-1,sy-1,gx-1,gy-1)

if  ans==-10**9:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

h,w,k= map(int, input().split())
sx,sy,gx,gy= map(int, input().split())
maze= [list(input()) for i in range(h)]


# 迷路　BFS
def clear_maze(sx, sy, gx, gy):

    INF=10**9
    distance = [[INF for i in range(w)] for j in range(h)]
    #    distance = [[None]*field_x_length]*field_y_length
    def bfs():
        # きた点と方向を格納
        d=deque()
        d.append((sx, sy))
        distance[sx][sy] =0

        while len(d):
            x, y = d.popleft()

            for i in range(0, 4):
                for j in range(1,k+1):
                    nx, ny = x + [j, 0, -j, 0][i], y + [0, j, 0, -j][i]
                    if not (0 <= nx < h and 0 <= ny < w):
                        break

                    elif maze[nx][ny] == '@' or distance[nx][ny]<=distance[x][y]:
                        break

                    elif distance[nx][ny] == INF:
                        d.append((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()

ans=clear_maze(sx-1,sy-1,gx-1,gy-1)

if  ans==10**9:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###



# 10のp乗の桁のmod 13
def coefficient(p):
    a = p % 6
    if a == 0:
        return 1
    if a == 1:
        return 10
    if a == 2:
        return 9
    if a == 3:
        return 12
    if a == 4:
        return 3
    if a == 5:
        return 4


def submit():
    s = input()
    clist = [c for c in s]
    n = len(clist)
    ansmod = 10 ** 9 + 7

    # dp[x][y] : 上位x桁まで見たときに、y mod 13になるパターン数
    dp = [
        [0 for _ in range(13)] for _ in range(n + 1)
    ]

    dp[0][0] = 1

    for i, c in enumerate(clist):
        if c == '?':
            for x in range(10):
                for y in range(13):
                    dig_mod = y
                    dig_mod += coefficient(n - i - 1) * x
                    dig_mod %= 13
                    dp[i + 1][dig_mod] += dp[i][y]
                    dp[i + 1][dig_mod] %= ansmod
        else:
            x = int(c)
            for y in range(13):
                dig_mod = y
                dig_mod += coefficient(n - i - 1) * x
                dig_mod %= 13
                dp[i + 1][dig_mod] += dp[i][y]
                dp[i + 1][dig_mod] %= ansmod

    print(dp[n][5] % ansmod)


if __name__ == '__main__':
    submit()

### FIXED CODE ###



# 10のp乗の桁のmod 13
def coefficient(p):
    a = p % 6
    if a == 0:
        return 1
    if a == 1:
        return 10
    if a == 2:
        return 9
    if a == 3:
        return 12
    if a == 4:
        return 3
    if a == 5:
        return 4


def submit():
    s = input()
    clist = [c for c in s]
    n = len(clist)
    ansmod = 10 ** 9 + 7

    # dp[x][y] : 上位x桁まで見たときに、y mod 13になるパターン数
    dp = [
        [0 for _ in range(13)] for _ in range(n + 1)
    ]

    dp[0][0] = 1

    for i, c in enumerate(clist):
        if c == '?':
            for x in range(10):
                for y in range(13):
                    dig_mod = y
                    dig_mod += coefficient(n - i - 1) * x
                    dig_mod %= 13
                    dp[i + 1][dig_mod] += dp[i][y]
                    dp[i + 1][dig_mod] %= ansmod
        else:
            x = int(c)
            for y in range(13):
                dig_mod = y
                dig_mod += coefficient(n - i - 1) * x
                dig_mod %= 13
                dp[i + 1][dig_mod] += dp[i][y]
                dp[i + 1][dig_mod] %= ansmod

    print(dp[n][5] % ansmod)


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

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

MOD = 10 ** 9 + 7

dp = [[0 for _ in range(m)] for _ in range(n)]
sd = [[0 for _ in range(m)] for _ in range(n)]

if s[0] == t[0]:
    dp[0][0] = 1
    sd[0][0] = 1

for i in range(1, n):
    if s[i] == t[0]:
        dp[i][0] = 1
    sd[i][0] = dp[i][0] + sd[i-1][0]

for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
    sd[0][j] = dp[0][j] + sd[0][j-1]

for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = (sd[i-1][j-1] + 1) % MOD
        sd[i][j] = (sd[i-1][j] + sd[i][j-1] - sd[i-1][j-1] + dp[i][j]) % MOD

#for i in range(n): print(dp[i])
#for i in range(n): print(sd[i])

ans = 0
for i in range(n):
    ans = (ans + sum(dp[i])) % MOD

print((ans + 1) % MOD)



### FIXED CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

MOD = 10 ** 9 + 7

dp = [[0 for _ in range(m)] for _ in range(n)]
sd = [[0 for _ in range(m)] for _ in range(n)]

ans = 1

if s[0] == t[0]:
    dp[0][0] = 1
    sd[0][0] = 1
    ans += 1

for i in range(1, n):
    if s[i] == t[0]:
        dp[i][0] = 1
        ans += 1
    sd[i][0] = dp[i][0] + sd[i-1][0]

for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
        ans += 1
    sd[0][j] = dp[0][j] + sd[0][j-1]

for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = (sd[i-1][j-1] + 1) % MOD
            ans = (ans + dp[i][j]) % MOD
        sd[i][j] = (sd[i-1][j] + sd[i][j-1] - sd[i-1][j-1] + dp[i][j]) % MOD

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

from sys import stdin
import math
import itertools
import re
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        cnt = 0
        L, R = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        for i in range(R-L):
            #print(i)
            cnt += cntAC(R-i-1, R-i, S)
        print(cnt)
    return
 

def cntAC(l, r, S):
    global dp
    global T
    if l+r not in dp:
        T[l+r] = S[l-1:r]
        t = T[l+r]
    if l+r not in dp:
        if t == 'AC':
            dp[l+r] = 1
        else:
            dp[l+r] = 0
    return dp[l+r]
 
 
def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N = int(input())
    a = list(map(int,input().split()))
    cnt = list()

    for i in range(min(a),max(a)+1):
        cnt.append(a.count(i-1)+a.count(i)+a.count(i+1))
    print(max(cnt))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N = int(input())
    a = list(map(int,input().split()))
    cnt = [0] * (max(a) + 2)

    for i in a:
        if i != 0:
            cnt[i-1] += 1
        cnt[i] += 1
        cnt[i+1] += 1
    print(max(cnt))

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

def solve():
    N, a, b = map(int, input().split())
    
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    # 必要なだけforを回す。N+1を書き換える
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)
    
    # nCr n個から重複を許さずr個の組み合わせを選ぶ
    def cmb(n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % MOD
    
    ans = 0
    for i in range(1, N+1):
        if i == a or i == b:
            continue
        ans += cmb(N, i) % MOD
    
    return ans % MOD

print(solve())

### FIXED CODE ###

def solve():
    n, a, b = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, max(a, b)+1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)
    
    def ncr(n, r):
        ret = factinv[r]
        for i in range(n, n-r, -1):
            ret = ret * i % MOD
        return ret
        
    ans = pow(2, n, MOD)
    ans = (ans-ncr(n, a)-ncr(n, b)-1) % MOD
    return ans


print(solve())
### BUGGY CODE ###

N,Q=[int(_) for _ in input().split()]
S=list(input())
hani=[[int(a) for a in input().split()] for j in range(Q)]
ACindex=[S[i]=="A" and S[i+1]=="C" for i in range(N-1)]
for j in hani:
    print(sum(ACindex[j[0]-1:j[1]-1]))

### FIXED CODE ###

#ACを検索して開始位置をインデックスにしておき、それを操作すれば多少はマシか
import numpy as np
N,Q=[int(_) for _ in input().split()]
S=list(input())
hani=[[int(a) for a in input().split()] for j in range(Q)]
ACindex=[0]
cur=0
for i in range(N-1):
    cur+=S[i]=="A" and S[i+1]=="C"
    ACindex.append(cur)
ACindex.append(cur)
for j in hani:
    print(ACindex[j[1]-1]-ACindex[j[0]-1])
### BUGGY CODE ###

n=int(input())
s=[0]*n
for i in range(n):
    s[i]=sorted(list(input()))
count=0
    
for i in range(1,n):
    for j in range(i):
    	if s[i]==s[j]:
        	count+=1

print(count)

### FIXED CODE ###

n = int(input())
count = 0
dic = {}
for _ in range(n):
    key = ''.join(sorted(input()))
    if key in dic:
        count += dic[key]
        dic[key] += 1
    else:
        dic[key] = 1
print(count)
### BUGGY CODE ###

# coding: utf-8
from itertools import count

def merge(A, left, mid, right, counter):
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [None]*(n2+1)
  for i in range(n1):
    L[i] = int(A[left + i])
  for i in range(n2):
    R[i] = int(A[mid + i])
  L[n1], R[n2] = float("inf"), float("inf")
  i, j = 0, 0
  for k in range(left, right):
    next(counter)
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1

def mergeSort(A, left, right, counter):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, counter)
    mergeSort(A, mid, right, counter)
    merge(A, left, mid, right, counter)

N = int(input())
A = input().split()
counter = count(0)
mergeSort(A, 0, len(A), counter)
print(*A)
print(next(counter))

### FIXED CODE ###

def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = list(A[left:left+n1]+[float("inf")]), list(A[mid:mid+n2]+[float("inf")])
  i = j = 0
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  counter += right - left
def mergeSort(A, left, right):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

N = int(input())
A = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[0]*n
ans=[0]*n
a=list(map(int,input().split()))

for _ in range(k):
  ans=[0]*n
  for i in range(n):
    left=max(0,i-a[i])
    right=min(n-1,i+a[i])
    #print(left,right)
    for j in range(left,right+1):
      ans[j]+=1
  a=ans

print(" ".join(map(str,a)))

### FIXED CODE ###

import math
n,k=map(int,input().split())
  
a=[0]*n
ans=[0]*n
a=list(map(int,input().split()))
check=math.ceil(math.log2(n))+1
if (k>=42):
  a=[n]*n
  print(" ".join(map(str,a)))
else:
  for _ in range(k):
    ans=[0]*n
    table=[0]*n
    for i in range(n):
      left=max(0,i-a[i])
      right=min(n-1,i+a[i])
      table[left]+=1
      if (right+1<n):
        table[right+1]-=1
      #print(left,right)
      #for j in range(left,right+1):
      #  ans[j]+=1
    #print(table)
    for i in range(1,n):
      table[i]+=table[i-1]
    a=table
 
  print(" ".join(map(str,a)))
### BUGGY CODE ###

from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= k**d[k] % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

from collections import deque
s=list(input())
n=len(s)
K=int(input())
d=deque()
l=[]
for i in range(n):
    d.append(s[i])
for i in range(n):
    buf=deque()
    for j in range(n-i):
        v=d.popleft()
        buf.append(v)
        l.append("".join((buf)))
    buf.popleft()
    d=buf
l=list(set(l))
l.sort()
#print(l)
print(l[K-1])

### FIXED CODE ###

from collections import deque
s=list(input())
K=int(input())
#max(K)=5でaaaaaはa,aa,aaa,aaaa,aaaaaの順
#よって5文字まで取れば良い
d=deque()
for i in range(len(s)):
    d.append(s[i])
comp=[]
#print(d)
for i in range(len(s)):
    buf=deque()
    for j in range(len(d)):
        v=d.popleft()
        buf.append(v)
        if j<5:
            comp.append("".join(buf))
    d=deque()
    for j in range(len(buf)):
        d.append(buf[j])
    d.popleft()
comp=list(set(comp))
comp.sort()
print(comp[K-1])
### BUGGY CODE ###

S = input()
S = list(map(int, S))

r = 0
pow10 = 1
counter = [0] * 2019
counter[0] = 1
for i in range(1, len(S) + 1):
    r = (r + pow10 * S[-i]) % 2019
    counter[r] += 1
    pow10 *= 10

ans = 0
for count in counter:
    if count >= 2:
        ans += count * (count - 1) // 2

print(ans)


### FIXED CODE ###

S = input()
S = list(map(int, S))

t = 1
r = 0
d = [0] * 2019
d[0] += 1
for n in reversed(S):
    r = (r + n * t) % 2019
    t = t * 10 % 2019
    d[r] += 1

ans = 0
for m in d:
    ans += m * (m-1) // 2

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

import sys
N,M = map(int,input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i],B[i] = map(int,input().split())
C = [set()]
if M != 0:
    C[0].add(A[0])
    C[0].add(B[0])
else:
    print(1)
    sys.exit()
for i in range(1,M):
    for j in range(len(C)):
        if A[i] in C[j]:
            C[j].add(B[i])
        elif B[i] in C[j]:
            C[j].add(A[i])
        else:
            C.append({A[i],B[i]})
ans = 0
for j in range(len(C)):
    if len(C[j]) > ans:
        ans = len(C[j])
print(ans)

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
N, M = map(int,input().split())
A = [None] * M
B = [None] * M
for i in range(M):
    A[i], B[i] = map(int,input().split())
uf = UnionFind(N)
for j,h in zip(A,B):
    uf.Unite(j,h)
print(min(uf.root)*(-1))
### BUGGY CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))
cards = list(map(int, input().split(" ")))

cards.sort()

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    insert_point = bisect.bisect_left(cards, rewrite_number)

    for _ in range(stock_count):
        cards.insert(insert_point, rewrite_number)
    
    del cards[:stock_count]

print(sum(cards))


### FIXED CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

print(total)