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

from collections import deque
n,x,y=map(int,input().split())
l=[[1]]
for i in range(1,n-1):
    l.append([i-1,i+1])
l.append([n-2])
x,y=x-1,y-1
l[x].append(y)
l[y].append(x)
#print(l)
p=[0 for i in range(n)]
for j in range(n):
    s=[-1 for i in range(n)]
    s[j]=0
    q=deque([j])
    while len(q)>0:
        a=q.popleft()
        for i in l[a]:
            if s[i]==-1:
                s[i]=s[a]+1
                q.append(i)
    for i in s:
        if i!=0:
            p[i]+=1
print(*map(lambda x:x//2,p[1:]),sep='\n')

### FIXED CODE ###

from collections import deque
n,x,y=map(int,input().split())
l=[[1]]
for i in range(1,n-1):
    l.append([i-1,i+1])
l.append([n-2])
x,y=x-1,y-1
l[x].append(y)
l[y].append(x)
#print(l)
p=[0 for i in range(n)]
for j in range(n):
    s=[-1 for i in range(n)]
    s[j]=0
    q=deque([j])
    while len(q)>0:
        a=q.popleft()
        for i in l[a]:
            if s[i]==-1:
                s[i]=s[a]+1
                q.append(i)
    for i in s:
        if i!=0:
            p[i]+=1
print(*map(lambda x:x//2,p[1:]),sep='\n')
### BUGGY CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

S = input()
N = len(S)
K = INT()

se = set()
for i in range(N):
    for j in range(i+1, N+1):
        T = S[i:j]
        se.add(T)
ans = sorted(se)
print(ans[K-1])


### FIXED CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

S = input()
N = len(S)
K = INT()

se = set()
for i in range(N):
    for j in range(i+1, min(i+6, N+1)):
        T = S[i:j]
        se.add(T)
ans = sorted(se)
print(ans[K-1])
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    for i in range(2, n):
        for num in numdct.keys():
            if(numdct[num] > 0):
                if(a[i] % num != 0):
                    numdct[num] -= 1
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] > 0):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)


### FIXED CODE ###


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    dellist = []
    for i in range(2, n):
        for num in numdct.keys():
            if(a[i] % num != 0):
                numdct[num] -= 1
                if(numdct[num] == 0):
                    dellist.append(num)
        for d in dellist:
            del numdct[d]
        dellist.clear()
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] > 0):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)
### BUGGY CODE ###

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

count = 0
for i in A:
    for j in A[count+1:]:
        if i == j:
            print("NO")
            break
    else:
        count += 1
        continue
    break
else:
    print("YES")


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(N-1):
    if A[i] == A[i+1]:
        print("NO")
        break
else:
    print("YES")
### BUGGY CODE ###

import math
n,k = map(int,input().split())
alist = list(map(int,input().split()))

for i in range(k):
    new = [0] * n
    for j in range(n):
        distance = j - alist[j]
        if distance < 0:
            distance = 0
        last =  j + alist[j]
        if last > n-1:
            last = n-1
        new[distance]+=1
        if last+1 < n:
            new[last+1]-=1
    for j in range(1,n):
        new[j] += new[j-1]
    alist = new.copy()
    if new.count(n) == n:
        break
print(*alist)

### FIXED CODE ###


import numpy as np
from numba import njit

import math

n,k = map(int,input().split())
a = np.array(input().split(),np.int64)

@njit
def solve(n,k,a):
    for i in range(k):
        new = np.zeros_like(a)
        for j in range(n):
            distance = j - a[j]
            if distance < 0:
                distance = 0
            last =  j + a[j]
            if last > n-1:
                last = n-1
            new[distance]+=1
            if last+1 < n:
                new[last+1]-=1
        a = np.cumsum(new)
        if np.all(a==n):
            break
    return a

a = solve(n,k,a)
print(" ".join(a.astype(str)))
### BUGGY CODE ###

N= int(input())
ans=0
for i in range(N-1):
    ans+=i+1
print(ans)

### FIXED CODE ###

N= int(input())
ans=N*(N-1)//2
print(ans)
### BUGGY CODE ###

from bisect import insort_left

X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
i = 0
j = 0
k = 0
while(True):
    try:
        if P[j] > Q[k]:
            if Q[k] < R[i]:
                insort_left(Q, R[i])
                k += 1
                i += 1
                continue
        else:
            if P[j] < R[i]:
                insort_left(P, R[i])
                j += 1
                i += 1
                continue
        break
    except IndexError:
        break
print(sum(P[j:]) + sum(Q[k:]))

### FIXED CODE ###

import heapq
 
X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
heapq.heapify(P)
heapq.heapify(Q)
i = 0
while(True):
    if P[0] >= R[i] and Q[0] >= R[i]:
        break
    if P[0] > Q[0]:
        if Q[0] < R[i]:
            heapq.heappop(Q)
            heapq.heappush(Q, R[i])
    else:
        if P[0] < R[i]:
            heapq.heappop(P)
            heapq.heappush(P, R[i])
    i += 1
    if i == len(R):
        break
print(sum(P) + sum(Q))
### BUGGY CODE ###

import sys
import math
from collections import deque

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

dp = [[10**9 for _ in range(K+1)] for _ in range(N)]
dp[0] = [0 for _ in range(K+1)]

for i in range(N):
    for l in range(K):
        if i-(l+1) >= 0:
            dp[i][l] = dp[i - (l + 1)][K] + abs(h[i] - h[i - (l + 1)])
        else:
            dp[i][l] = min(dp[i])
        if l == K-1:
            dp[i][K] = min(dp[i])
print(min(dp[N-1]))

### FIXED CODE ###

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

dp = [[10**9 for _ in range(K+1)] for _ in range(N)]
dp[0] = [0 for _ in range(K+1)]

for i in range(N):
    for l in range(K):
        if i-(l+1) >= 0:
            dp[i][l] = dp[i - (l + 1)][K] + abs(h[i] - h[i - (l + 1)])
        else:
            dp[i][l] = min(dp[i])
        if l == K-1:
            dp[i][K] = min(dp[i])
print(min(dp[N-1]))
### BUGGY CODE ###

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

ans = 1
threshold = 10 ** 18
for i in range(n):
    ans *= a[i]
if threshold < ans:
    ans = -1

print(ans)

### FIXED CODE ###

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

ans = 1
threshold = 10 ** 18
if 0 in a:
    ans = 0
for i in range(n):
    ans *= a[i]
    if threshold < ans:
        ans = -1
        break

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

N = int(input())
H = [i for i in map(int, input().split())]
ans ='Yes'
for idx in range(N):
  k = H[idx]
  for j in range(idx+1, N):
    if k - H[j] > 1:
      ans = 'No'
print(ans)
    

### FIXED CODE ###

N = int(input())
H = [i for i in map(int, input().split())]
ans ='Yes'
temp_max =H[0]
for idx in range(N):
  if temp_max - H[idx] > 1:
    ans = 'No'
    break
    
  if temp_max < H[idx]:
    temp_max=H[idx]
  
print(ans)
### BUGGY CODE ###

#AGC030 B - Powers of two
beki=[]
for i in range(1,32):
    beki.append(2**i)#bekiは２のべき乗の配列
N=int(input())
A=input().split()
for i in range(N):
    A[i]=int(A[i])
sorted(A)#Aを昇順にソート
for i in (reversed(beki)):
    inverseA=[]
    for j in range(len(A)):
        inverseA.append(i-A[j])#inverseA
    for j in range(len(A)):
        if inverseA[j] in A:
            A.remove(inverseA[j])
print((N-len(A))//2)

### FIXED CODE ###

#AGC030 B - Powers of two
import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv==2*a and cnter[inv-a]<=1:
      	continue
    if cnter[inv-a]>0:
        cnter[inv-a]=cnter[inv-a]-1
        cnter[a]=cnter[a]-1
        ans=ans+1
print(ans)
### BUGGY CODE ###

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

if min(A) == 0:
    ans = 0
else:
    for i in A:
        ans *= i
    if ans > 10**18:
        ans = -1

print(ans)

### FIXED CODE ###

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

if min(A) == 0:
    print(0)
    exit()

for i in A:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

def main():
  N=int(input())
  A=list(map(int,input().split()))
  x=0
  for i in range(N):
    for j in range(N):
      if i==j:
        pass
      elif A[i]%A[j]==0:
        break
    else:
      x+=1
  print(x)
main()

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
AM=max(A)+1
B=[0]*AM
x=0
for i in A:
  for j in range(i,AM,i):
    B[j]+=1
for i in A:
  if B[i]==1:
    x+=1
print(x)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = []
b = []
c = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            b.append([i, j])
        else:
            c.append([i, j])

ans = 0
for x in c:
    tmp = inf
    for y in b:
        tmp = min(tmp, abs(x[0]-y[0])+abs(x[1]-y[1]))
        if tmp <= ans:
            break
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]

d = [[-1] * w for _ in range(h)]


def bfs():
    s = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                s.append([j, i])

    q = deque()
    for sx, sy in s:
        q.append([sx, sy])
        d[sy][sx] = 0
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy
            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 and a[vy][vx] == "." and d[vy][vx] == -1:
                d[vy][vx] = d[uy][ux] + 1
                q.append([vx, vy])


bfs()

ans = 0
for row in d:
    for e in row:
        ans = max(ans, e)

print(ans)


### FIXED CODE ###

from scipy.ndimage import distance_transform_cdt


def main():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


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

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        tmp = [0] * n
        count = 0
        for j in range(n):
            for k in range(max(0, j - a[j]), min(n, j + a[j] + 1)):
                tmp[k] += 1
                if tmp[k] == n:
                    count += 1
        a = tmp
        if count == n:
            break
    print(*a)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from itertools import accumulate


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k):
        tmp = [0] * (n + 1)
        for j in range(n):
            tmp[max(0, j - a[j])] += 1
            tmp[min(n, j + a[j] + 1)] -= 1
        a = list(accumulate(tmp))[:n]
        for ai in a:
            if ai != n:
                break
        else:
            break
    print(*a)


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

# -*- coding: utf-8 -*-
from collections import deque

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


monster = deque()
def main():
    h = input_int()

    monster.append(h)

    cnt = 0
    while len(monster) != 0:
        cnt += 1
        temp = monster.popleft()
        if temp != 1:
            val = temp // 2
            monster.append(val)
            monster.append(val)

    return cnt


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h = input_int()

    result = 0
    mon_cnt = 1
    while h != 0:
        result += mon_cnt
        mon_cnt *= 2
        h = (h // 2)

    return result


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


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

if K <= A:
    print(K)
elif A + B >= K:
    print(A)
else:
    total = 0
    for i in range(1, K+1):
        if i <= A:
            total += 1
        elif i > A+B:
            total -= 1
    print(total)


### FIXED CODE ###


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

if K <= A:
    print(K)
elif A + B >= K:
    print(A)
else:
    total = 0
    K -= A
    total += A
    K -= B
    total = total - (K)
    print(total)
### BUGGY CODE ###

N=int(input())

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

S=1

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

if S>10**18:
    print(-1)
else:
    print(S)


### FIXED CODE ###

N=int(input())

A=list(map(int,input().split()))
ans=0
S=1
if 0 in A:
    print(0)
else:
    for i in range(N):
        S=S*A[i]
        if S>10**18:
            print(-1)
            ans=1
            break
    if ans==0:
        print(S)
### BUGGY CODE ###

from itertools import product
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(len(s)):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    elif s[i] == 'B':
        b.append(i)

lst = list(product(r,g,b))
ans = 0
for i in range(len(lst)):
    tmp = sorted(lst[i])
    if tmp[1]-tmp[0] != tmp[2]-tmp[1]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = 0
g = 0
b = 0
for x in s:
    if x == 'R':
        r += 1
    elif x == 'G':
        g += 1
    elif x == 'B':
        b += 1

ng_cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            continue
        else:
            k = 2 * j - i
            if k < n and s[i] != s[k] and s[j] != s[k]:
                ng_cnt += 1

print(r * g * b - ng_cnt)
### BUGGY CODE ###

def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [0] * (H+1)
    for x in range(1, H+1):
        dp[x] = min(dp[max(x-a, 0)] + b for a, b in zip(A, B))

    print(dp[H])
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [0] * (H+1)
    for x in range(1, H+1):
        dp[x] = min(dp[max(x-a, 0)] + b for a, b in zip(A, B))

    print(dp[H])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline

inf = float('inf')

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    es.append((int(input()), 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = inf
check_needed = True
d_cnt = 0
for time, typ, pos in es:
    if typ == 1:
        st.add(pos)
        if pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = inf
            check_needed = False
        print(cur_min_stop if cur_min_stop < inf else -1)
        d_cnt += 1
        if d_cnt == Q:
            break


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

import math
K=int(input())
sum=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            gcd1 = int(math.gcd(a,b))
            gcd2 = int(math.gcd(b,c))
            gcd = int(math.gcd(gcd1,gcd2))

            sum = sum+gcd
print(sum)

### FIXED CODE ###

from math import gcd

K = int(input())
out = 0
Count = [0]*K
gcds = [[0]*K for i in range(K)]

for i in range (1,K+1):
    for j in range(1,+K+1):
        value = gcd(i,j)
        gcds[i-1][j-1]=value
        Count[value-1]+=1

for i in range(1,K+1):
    for j in range(1,K+1):
        out +=gcds[i-1][j-1]*Count[j-1] #値*回数
        
print(out)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush


def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    heapify(A)
    
    for _ in range(M):
        B, C = map(int, input().split())
        for _ in range(B):
            if A[0] < C:
                heappop(A)
                heappush(A, C)
            else:
                break
    
    print(sum(A))


if __name__ == '__main__':
    solve()

### FIXED CODE ###

from operator import itemgetter


def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = [[] for _ in range(M)]
    for i in range(M):
        BC[i] = list(map(int, input().split()))
    BC.sort(key=itemgetter(1), reverse=True)
    
    change = []
    for b, c in BC:
        change += [c for _ in range(b)]
        if N < len(change):
            break
    
    A += change
    A.sort()
    ans = sum(A[-N:])
    print(ans)


if __name__ == '__main__':
    solve()