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

N = int(input())

dic = dict()

for i in range(N):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

# dic = sorted(dic.items(), key=lambda x:x[0])

max_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]

max_list.sort()

for lis in max_list:
  print(lis)


### FIXED CODE ###

N = int(input())

s = [None for _ in range(N)]

for i in range(N):
  s[i] = input()

s.sort()

max_list = []
max_v = 1

count = 1
prev = s[0]


for i in range(1, N):
  # print(s[i], prev, count)
  if s[i] == prev:
    count += 1
  else:
    if max_v == count:
      max_list.append(prev)
    elif max_v < count:
      max_list = [prev]
      max_v = count
    count = 1
    prev = s[i]


if max_v == count:
  max_list.append(prev)
elif max_v < count:
  max_list = [prev]
  max_v = count

for k in max_list:
  print(k)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(input())

tree = [[] for _ in range(N)]

for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append((b,c))
    tree[b].append((a,c))

Q, K = map(int, input().split())

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(depth[x-1] + depth[y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(input())

tree = [[] for _ in range(N)]

for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append((b,c))
    tree[b].append((a,c))

Q, K = map(int, input().split())

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(depth[x-1] + depth[y-1])
### BUGGY CODE ###

def xor(hoge):
    res = hoge[0]
    for i in range(1,len(hoge)):
        res = res ^ hoge[i]
    return res

# O(n^2) 解法
def debug():
    N = int(input())
    A = list(map(int,input().split()))
    cnt = 0
    note = []
    for i in range(N):
        for j in range(i+1,N+1):
            part = A[i:j]
            res = xor(part)
            if res == sum(part):
                print(i,j)
                cnt += 1
                part_bin = [format(e,"b") for e in part]
                note.append(part_bin)
    print(cnt)

#---------メインコード----------#

def main():
    import sys
    sys.setrecursionlimit(10**9)
    N = int(input())
    A = list(map(int,input().split()))
    def syakutori(l=0,r=0,res=0,sum_=0,ans=[]):
        if l == N and r == N:
            return len(list(set((ans))))
        note = r
        for i in range(r,N):
            if res ^ A[i] == sum_ + A[i]:
                r += 1
                res += A[i]
                sum_ += A[i]
            else:
                break
        length = r - l
        f = note == r
        if f is False:
            for i in range(l,r+1):
                for j in range(i+1,r+1):
                    ans.append((i,j))
        #print(l,r)
        if length == 0:
            r += 1
        else:
            res -= A[l]
            sum_ -= A[l]
        return syakutori(l+1,r,res,sum_,ans)
    ans = syakutori()
    print(ans)

main()

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
r = 0; sum_ = 0; res = 0; ans = 0
for l in range(N+1):
    for i in range(r,N):
        if res ^ A[i] == sum_ + A[i]:
            r += 1
            res += A[i]
            sum_ += A[i]
        else:
            break
    length = r - l
    ans += length
    if length == 0:
        r += 1
    else:
        res -= A[l]
        sum_ -= A[l]

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

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def II(): return int(input())
def LI(): return [int(i) for i in input().split()]
 
N, K = LI()
H = LI()
 
cost = [0] * N
cost[0] = 0
for n in range(1, N):
  MIN = min(
  	[ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ]
  )
  cost[n] = MIN
 
print(cost[-1])

### FIXED CODE ###

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

a_li.sort()

ans = 0

a_set = set(a_li)

check = [0] * (a_li[-1]+2)
for i in range(a_li[-1]+1):
    check[i] = a_li.count(i)

for i in a_set:
    s = check[i] + check[i-1] + check[i+1]
    
    ans = max(ans,s)

print(ans)

### FIXED CODE ###

from collections import defaultdict

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

a_li.sort()
a_count = defaultdict(int)
for x in a_li:
    a_count[x] += 1

ans = 0

a_set = set(a_li)

for i in a_set:
    s = a_count[i] + a_count[i-1] + a_count[i+1]
    ans = max(ans,s)

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

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

count = 0
odd = ""

while True:
    for i, n in enumerate(a):
        if n % 2 == 0:
            a[i] == n / 2
            count += 1
        else:
            odd = "finish"
            break
    if odd == "finish":
        break
print(count)


### FIXED CODE ###

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

ans = a[0]
for i in range(int(n)):
    count = 0
    while(a[i] % 2 == 0):
        a[i] /= 2
        count += 1
    ans = min(ans, count)
print(ans)
### BUGGY CODE ###

from fractions import gcd

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

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


ans = 0
for a in A:
    ans += lcm // a
    if ans >= MOD:
        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 ###

def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    r = [[float("inf")]*n for i in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                r[i][j] = min(d[i][j],r[i][k] + r[k][j])
    return r

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()


war = warshall_floyd(n,a)

res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)


### FIXED CODE ###

def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    r = [[float("inf")]*n for i in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                r[i][j] = min(d[i][j],r[i][k] + r[k][j])
    return r

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()


war = warshall_floyd(n,a)

res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)
### BUGGY CODE ###

# -*- coding:utf-8 -*-

n = int(input())
print(n,':',sep='',end=' ')
array = []
count = 0
while True:
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n-1:
            count += 1
            break
    if count == 10:
        break
array.append(n)
for i in range(len(array)):
    print(array[i],end=' ')
print('')

### FIXED CODE ###

# -*- coding:utf-8 -*-

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    if n == 999993031:
        break
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 24:
        break

array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')
### BUGGY CODE ###

X = input()
while 'ST' in X:
    X = X.replace('ST','')
print(len(X))


### FIXED CODE ###

X = list(input())
c = 0
for x in X:
    if x=='S':
        c += 1
    else:
        if c > 0:
            c -= 1
print(2*c)
### BUGGY CODE ###

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

p = list(map(int,input().split()))

from collections import deque
q = deque()

for i in range(n-k+1):
    if i==0:
        for j in range(k):
            mu = (p[j]+1)/2
            q.append(mu)
            M = sum(q)
    else:
        q.popleft()
        mu = (p[i+k-1]+1)/2
        q.append(mu)
        m = sum(q)
        M = max(m,M)

print(M)

### FIXED CODE ###

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

ls_mu = []
for i in range(n):
    mu = (p[i]+1)/2
    ls_mu.append(mu)
# print(ls_mu)
m = 0
M = 0
for i in range(n-k+1):
    if i==0:
        for j in range(k):
            m += ls_mu[j]
        M += m
    else:
        l = ls_mu[i-1]
        r = ls_mu[i+k-1]
        m = m - l + r
        M = max(m,M)

print(M)
### BUGGY CODE ###

d, n = map(int, input().split())
cnt = 0
i = 0
while cnt < n:
  i += 1
  div, mod = divmod(i, 100**d)
  if mod == 0 and div == d:
    cnt += 1
print(i)


### FIXED CODE ###

d, n = map(int, input().split())
cnt = 0
i = 0
while cnt < n:
  i += 1
  if i % 100**d == 0 and i % 100**(d+1) != 0:
    cnt += 1
print(i)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
ans = pow(2, n) - 1
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

print((ans - C(n, a) - C(n, b)) % mod)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
ans = power(2, n) - 1
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

print((ans - C(n, a) - C(n, b)) % mod)
### BUGGY CODE ###

# B
import numpy as np
np.random.seed(123)
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []

for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    
# find minimum degree
sv = np.array([len(G[k]) for k in range(1, N+1)])
s = np.random.choice(np.arange(N)[sv == min(sv)]) + 1

targets = dict()
for a in G[s]:
    targets[a] = 1


# BFS from st
t = G[s][0]
pt = [s, t]
del targets[t]
while len(targets) > 0:
    ques = deque()
    visited = [0]*(N+1)    
    for a in pt:
        visited[a] = 1
    ques.append([t, pt])
    end = 0
    while len(ques) > 0 and end == 0:
        q = ques.popleft()
        s = q[0]
        pt = q[1]
        for t in G[s]:
            if visited[t] == 1:
                pass
            elif t in targets.keys():
                pt.append(t)
                end = 1
                del targets[t]
                break
            else:
                visited[t] = 1
                ques.append([t, pt+[t]])
            

# BFS from end
visited = [0]*(N+1)
for a in pt:
    visited[a] = 1
sv = np.array([len([l for l in G[k] if visited[l] == 0]) if visited[k] == 0 else N for k in range(1, N+1)])

# need calculation
if len([l for l in G[t] if visited[l] == 0]) != 0:
    endp = np.random.choice(np.arange(N)[sv == min(sv)]) + 1
    targets = dict()
    for a in G[endp]:
        if visited[a] == 0:
            targets[a] = 1
    while len(targets) > 0:
        ques = deque()
        visited = [0]*(N+1)    
        for a in pt:
            visited[a] = 1
        visited[endp] = 1
        ques.append([t, pt])
        end = 0
        while len(ques) > 0 and end == 0:
            q = ques.popleft()
            s = q[0]
            pt = q[1]
            for t in G[s]:
                if visited[t] == 1:
                    pass
                elif t in targets.keys():
                    pt.append(t)
                    end = 1
                    del targets[t]
                    break
                else:
                    visited[t] = 1
                    ques.append([t, pt+[t]])
    pt.append(endp)
        
print(len(pt))
print(" ".join([str(a) for a in pt]))

### FIXED CODE ###

# B
import numpy as np
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []
    
visited = [0]*(N+1)
for m in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    if m == 0:
        pt = [A, B]
        visited[A] = 1
        visited[B] = 1

# from left
s = pt[0]
add_left = list()

while True:
    left_ext = [l for l in G[s] if visited[l] == 0]
    if len(left_ext) != 0:
        s = left_ext[0]
        visited[s] = 1
        add_left.append(s)
    else:
        break

# from right
s = pt[1]
add_right = list()

while True:
    right_ext = [l for l in G[s] if visited[l] == 0]
    if len(right_ext) != 0:
        s = right_ext[0]
        visited[s] = 1
        add_right.append(s)
    else:
        break
pt = list(reversed(add_left)) + pt + add_right
print(len(pt))
print(" ".join([str(a) for a in pt]))
### BUGGY CODE ###

def examD():
    N = I()
    g, s, c = [0]*2, [0]*2, [0]*2
    for i in range(2):
        g[i],s[i],c[i] = LI()
    dp1 = [0]*(N+1)
    v1 = [g[1]-g[0],s[1]-s[0],c[1]-c[0]]
    w1 = [g[0],s[0],c[0]]
    v2 = [g[0]-g[1],s[0]-s[1],c[0]-c[1]]
    w2 = [g[1],s[1],c[1]]
    for i in range(N):
        if i+w1[0]<=N:
            dp1[i+w1[0]] = max(dp1[i+w1[0]],dp1[i]+v1[0])
        if i+w1[1]<=N:
            dp1[i+w1[1]] = max(dp1[i+w1[1]],dp1[i]+v1[1])
        if i+w1[2]<=N:
            dp1[i+w1[2]] = max(dp1[i+w1[2]],dp1[i]+v1[2])
    newN = max(dp1)+N
#    print(newN)
    dp2 = [0]*(newN+1)
    for i in range(newN):
        if v2[0]>0 and i+w2[0]<=newN:
            dp2[i+w2[0]] = max(dp2[i+w2[0]],dp2[i]+v2[0])
        if v2[1]>0 and i+w2[1]<=newN:
            dp2[i+w2[1]] = max(dp2[i+w2[1]],dp2[i]+v2[1])
        if v2[2]>0 and i+w2[2]<=newN:
            dp2[i+w2[2]] = max(dp2[i+w2[2]],dp2[i]+v2[2])
    ans = max(dp2)+newN
    print(ans)

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


### FIXED CODE ###

def examD():
    N = I()
    g, s, c = [0]*2, [0]*2, [0]*2
    for i in range(2):
        g[i],s[i],c[i] = LI()
    dp1 = [0]*(N+1)
    v1 = [g[1]-g[0],s[1]-s[0],c[1]-c[0]]
    w1 = [g[0],s[0],c[0]]
    v2 = [g[0]-g[1],s[0]-s[1],c[0]-c[1]]
    w2 = [g[1],s[1],c[1]]
    for i in range(N):
        if i+w1[0]<=N:
            dp1[i+w1[0]] = max(dp1[i+w1[0]],dp1[i]+v1[0])
        if i+w1[1]<=N:
            dp1[i+w1[1]] = max(dp1[i+w1[1]],dp1[i]+v1[1])
        if i+w1[2]<=N:
            dp1[i+w1[2]] = max(dp1[i+w1[2]],dp1[i]+v1[2])
    newN = max(dp1)+N
#    print(newN)
    dp2 = [0]*(newN+1)
    for i in range(newN):
        if v2[0]>0 and i+w2[0]<=newN:
            dp2[i+w2[0]] = max(dp2[i+w2[0]],dp2[i]+v2[0])
        if v2[1]>0 and i+w2[1]<=newN:
            dp2[i+w2[1]] = max(dp2[i+w2[1]],dp2[i]+v2[1])
        if v2[2]>0 and i+w2[2]<=newN:
            dp2[i+w2[2]] = max(dp2[i+w2[2]],dp2[i]+v2[2])
    ans = dp2[newN]+newN
    print(ans)

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list()
for i in range(M):
  A.append(int(input()))
ans = list()
for i in range(N+1):
  if(i in A):
    ans.append(0)
  elif(i == 0 or i == 1):
    ans.append(1)
  else:
    ans.append((ans[i-1]+ans[i-2])%1000000007)
print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
mod = 10**9 + 7
ans = [0] * (N+1)
ans[0] = 1
ans[1] = 1 if 1 not in A else 0
for i in range(2, N+1):
  ans[i] = (ans[i-1]+ans[i-2])%mod if i not in A else 0
print(ans[N])
### BUGGY CODE ###

a = input()
a = int(a)

suuretu_list = []
kari_list = []

for i in range(a):
    b = int(input())
    suuretu_list.append(b)
    kari_list.append(b)

c = max(suuretu_list)

d = suuretu_list.index(c)

for u in suuretu_list:
    if u != c:
        print(c)
    else:
        e = max(kari_list)
        f = kari_list.index(e)
        kari_list.pop(f)
        g = max(kari_list)
        print(g)
        kari_list.append(g)

### FIXED CODE ###

a = input()
a = int(a)

suuretu_list = []
kari_list = []

for i in range(a):
    b = int(input())
    suuretu_list.append(b)
    kari_list.append(b)

kari_list = sorted(kari_list)

c = max(suuretu_list)

d = suuretu_list.index(c)

for u in suuretu_list:
    if u != c:
        print(c)
    else:
        print(kari_list[-2])
### BUGGY CODE ###

#abc176-d
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]

#DPで遷移が2種類　初期値をinf として、現在値より小さければ遷移可能とする
dp = [ [float('inf') ]*W  for _ in range(H)]

q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    nh,nw = q.popleft()
    #徒歩での遷移
    if nh>0 and s[nh-1][nw] =='.' and dp[nh-1][nw]>dp[nh][nw]:
        q.append((nh-1,nw))
        dp[nh-1][nw] = dp[nh][nw]
    if nh<H-1 and s[nh+1][nw] =='.' and dp[nh+1][nw]>dp[nh][nw]:
        q.append((nh+1,nw))
        dp[nh+1][nw] = dp[nh][nw]
    if nw>0 and s[nh][nw-1] =='.' and dp[nh][nw-1]>dp[nh][nw]:
        q.append((nh,nw-1))
        dp[nh][nw-1] = dp[nh][nw]
    if nw<W-1 and s[nh][nw+1] =='.' and dp[nh][nw+1]>dp[nh][nw]:
        q.append((nh,nw+1))
        dp[nh][nw+1] = dp[nh][nw]
    #ワープで遷移
    for ih in range(-2,3,1):
        for iw in range(-2,3,1):
            if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                    q.append((nh+ih,nw+iw))
                    dp[nh+ih][nw+iw] = dp[nh][nw]+1


ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)    
    




### FIXED CODE ###

#abc176-d
import sys,math,collections,itertools
input = sys.stdin.readline
 
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]
 
#DPで遷移が2種類　初期値をinf として、現在値より小さければ遷移可能とする
dp = [ [float('inf') ]*W  for _ in range(H)]
 
q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    visit = []
    while q:
        nh,nw = q.popleft()
        visit.append((nh,nw))
        #徒歩での遷移
        if nh>0 and s[nh-1][nw] =='.' and dp[nh-1][nw]>dp[nh][nw]:
            q.append((nh-1,nw))
            dp[nh-1][nw] = dp[nh][nw]
        if nh<H-1 and s[nh+1][nw] =='.' and dp[nh+1][nw]>dp[nh][nw]:
            q.append((nh+1,nw))
            dp[nh+1][nw] = dp[nh][nw]
        if nw>0 and s[nh][nw-1] =='.' and dp[nh][nw-1]>dp[nh][nw]:
            q.append((nh,nw-1))
            dp[nh][nw-1] = dp[nh][nw]
        if nw<W-1 and s[nh][nw+1] =='.' and dp[nh][nw+1]>dp[nh][nw]:
            q.append((nh,nw+1))
            dp[nh][nw+1] = dp[nh][nw]
    while visit:
    #ワープで遷移
        nh,nw = visit.pop()
        for ih in range(-2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
     
 
ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)
### BUGGY CODE ###

n = int(input())
ans = 1
if n == 1:
    print(1)
    exit()
else:
    for i in range(1, n+1):
        ans *= i

print(ans%(10**9+7))

### FIXED CODE ###

import math

n = int(input())

print(int(math.factorial(n)) % (10**9+7))
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
data = [list(map(int,input().split())) for i in range(M)]

A.sort()

from operator import itemgetter

data = sorted(data,key = itemgetter(1),reverse=True)

B = []
for i,j in data:
    B += [j]*i

for i in range(min(N,len(B))):
    if A[i] < B[i]:
        A[i] = B[i]
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
data = [list(map(int,input().split())) for i in range(M)]

A.sort()

from operator import itemgetter

data = sorted(data,key = itemgetter(1),reverse=True)

B = []
for i,j in data:
    if len(B) > N:
        break
    else:
        B += [j]*i

for i in range(min(N,len(B))):
    if A[i] < B[i]:
        A[i] = B[i]
print(sum(A))