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

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))
    return ret


# A = []
# for _ in range(N):
#     import random
#     A.append(random.randint(1, 3))
# ans = test(A)
# print(ans)


# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 何個続くかを持つ
counts = []
n = None
cnt = 0
for a in A:
    if n != a:
        n = a
        cnt = 0
        counts.append((n, 0))
    cnt += 1
    counts[-1] = (n, cnt)

while len(counts) >= 2 or counts[0][1] > 1:
    counts = convert(counts)
print(counts[0][0])


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))

    n = None
    count = 0
    filtered = []
    for a, cnt in ret:
        if a != n:
            n = a
            count = 0
            filtered.append((n, 0))
        count += cnt
        filtered[-1] = (n, count)
    return filtered

#
# A = []
# for _ in range(N):
#     import random
#
#     A.append(random.randint(0, 2))
# ans = test(A)
# print(ans)

# cnt2[n]: n! が 2 で何回割れるか
cnt2 = []
cnt = 0
for n in range(N + 10):
    while n >= 2 and n % 2 == 0:
        n //= 2
        cnt += 1
    cnt2.append(cnt)

# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 1が入ってるとき、2は0と同一視できる
if 1 in A:
    for i in range(len(A)):
        if A[i] == 2:
            A[i] = 0
mod = 2 if 1 in A else 4

ans = 0
n = len(A) - 1
for r in range(len(A)):
    cnt = cnt2[len(A) - 1] - cnt2[r] - cnt2[n - r]
    # cnt = math.factorial(n) // math.factorial(r) // math.factorial(n - r)
    if cnt == 0:
        ans += A[r]
        ans %= mod
    # print(n, r, cnt)
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    cnt=0
    l,r=map(int,input().split())
    for j in range(l,r):
        #print(s[j-1:j+1])
        if s[j-1:j+1]=="AC":
            cnt+=1
    print(cnt)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input().replace("\n","")
cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    if s[i-1:i+1]=="AC":
        cnt[i]+=1
    cnt[i]+=cnt[i-1]
#print(cnt)
for i in range(q):
    a,b=map(int,input().split())
    print(cnt[b-1]-cnt[a-1])
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
        sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((ans+1)%mod)

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i - 1][j] + sumdp[i][j - 1] +1
#            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %=mod
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(0,100000,1):
        for j in range(0,-100000,-1):
            if i == j:
                 continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-119,119):
        for j in range(-119,119):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import math
import numpy as np
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
num_list =  input().split(' ')
num_list2 = [int(n) for n in num_list]
num_list3 = [0]*n
num_list4 = [0]*n
num_list5 = [0]*n
for i in range(len(num_list2)):
    num_list3[num_list2[i]-1] += 1
for i in range(len(num_list2)):
    size = max(0 , num_list3[num_list2[i]-1])
    if size >= 2:
        ans = comb(size,2)
    elif size == 1:
        ans = 0
    else :
        ans = 0 
    num_list4[num_list2[i]-1] = ans

    size = max(0 , num_list3[num_list2[i]-1]-1)
    if size >= 2:
        ans = comb(size,2)
    elif size == 1:
        ans = 0
    else :
        ans = 0 
    num_list5[num_list2[i]-1] = ans
sum_V = np.sum(num_list4)
for i in range(n):
    print(num_list5[num_list2[i]-1]-num_list4[num_list2[i]-1]+sum_V)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = [0] * n
for i in a:
    cnt[i-1] += 1
total = [0] * n
for i in range(n):
    total[i] = cnt[i] * (cnt[i] - 1) // 2
total_sum = sum(total)
for i in a:
    ans = total_sum
    ans -= total[i-1]
    ans += (cnt[i-1] - 1) * (cnt[i-1] - 2) // 2
    print(ans)
### BUGGY CODE ###


from collections import Counter
mod=10**9+7
N=10**5+11
fac,finv,inv = [0]*N,[0]*N,[0]*N

def cmb_init():
        fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1
        for i in range(2,N):
                fac[i] = fac[i-1]*i%mod
                inv[i] = mod-inv[mod%i] * (mod//i) % mod
                finv[i] = finv[i-1] * inv[i] % mod


def cmb_mod(n,k):
        if n<k : return 0
        return fac[n]*(finv[k]*finv[n-k]%mod)%mod

n=int(input())
a=list(map(int,input().split()))
ac = Counter(a)
sames=[i for i,x in enumerate(a) if x==ac.most_common()[0][0]]
same_len = sames[0]+(n-sames[1])
cmb_init()
print(n)

for i in range(1,n):
        print(cmb_mod(n+1,i+1) - cmb_mod(same_len,i))
print(1)

### FIXED CODE ###

from collections import Counter
mod=10**9+7
N=10**5+11
fac,finv,inv = [0]*N,[0]*N,[0]*N
 
def cmb_init():
        fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1
        for i in range(2,N):
                fac[i] = fac[i-1]*i%mod
                inv[i] = mod-inv[mod%i] * (mod//i) % mod
                finv[i] = finv[i-1] * inv[i] % mod
 
 
def cmb_mod(n,k):
        if n<k : return 0
        return fac[n]*(finv[k]*finv[n-k]%mod)%mod
 
n=int(input())
a=list(map(int,input().split()))
ac = Counter(a).most_common()[0][0]
sames=[i for i,x in enumerate(a) if x==ac]
same_len = sames[0]+(n-sames[1])
cmb_init()
print(n)
 
for i in range(1,n):
        nums = cmb_mod(n+1,i+1) - cmb_mod(same_len,i)
        if nums < 0: nums+=mod
        print(nums)
print(1)
### BUGGY CODE ###

import sys
import bisect
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
for i in range(1,n-1):
    base = l_dict[i]
    next_base = l_dict[i+1]
    for l in l_ls[:i]:
        bisect.insort_left(_sum_ls, l + base)
    for _sum in _sum_ls[::-1]:
        if next_base < _sum:
            cnt += 1
        else:
            break
print(cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    L = [i+A[i-1] for i in range(1,N+1)]
    R = [i-A[i-1] for i in range(1,N+1)]
    import collections
    Lcnter = collections.Counter(L)
    Rcnter = collections.Counter(R)
    limit = max(max(Lcnter.keys()), max(Rcnter.keys()))
    ans = 0
    for i in range(limit+1):
        if i in L and i in R:
            ans += Lcnter[i]*Rcnter[i]
    print(ans)
    


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    L = [i+A[i-1] for i in range(1,N+1)]
    R = [i-A[i-1] for i in range(1,N+1)]
    import collections
    Lcnter = collections.Counter(L)
    Rcnter = collections.Counter(R)
    values = set(Lcnter.keys()) & set(Rcnter.keys())
    ans = 0
    for i in values:
        ans += Lcnter[i]*Rcnter[i]
    print(ans)
    


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

import string

N = int(input())

CountList = []

atoz = string.ascii_lowercase
for i in range(N):
    temp = ''
    s=input()
    CountList.append(''.join(sorted(s)))

count = 0
for i,str1 in enumerate(CountList[:-1]):
    for str2 in CountList[i+1:]:
        if str1==str2:
            count+=1

print(count)

### FIXED CODE ###

import string
import collections

N = int(input())

CountList = []

atoz = string.ascii_lowercase
for i in range(N):
    temp = ''
    s=input()
    CountList.append(''.join(sorted(s)))

str = collections.Counter(CountList)

count = 0
for s in str:
    count += sum(range(str[s]))

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

def main():
    from numba import njit, i8, void
    import numpy as np
    h, w, K = map(int, input().split())
    grid = np.array([list(map(int, list(input())))
                     for _ in [0]*h], dtype=np.int16)
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]
        memo = [0]+[j for j in range(1, h) if i[j-1] != i[j]]+[h]
        ans = len(memo)-1
        memo = np.array(memo, dtype=np.int64)
        @njit(cache=True)
        def a(memo):
            j = 0
            flag = False
            memo2 = np.zeros(len(memo)-1, dtype=np.int64)
            ans2 = [0]
            while j < w:
                if flag:
                    break
                p, l = memo[0], ans2[-1]
                for k, q in enumerate(memo[1:ans+1]):
                    memo2[k] += np.sum(grid[p:q, j])
                    p = q
                    if memo2[k] > K:
                        ans2.append(j)
                        memo2 = np.zeros(ans, dtype=np.int64)
                        if j == l:
                            flag = True
                        l = j
                        break
                else:
                    j += 1
            if not flag:
                return len(ans2)
            else:
                return 10**8
        m = min(m, ans+(a(memo)-2))
    print(m)


main()

### FIXED CODE ###

def main():
    from itertools import product
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**h):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()
### BUGGY CODE ###

n, k, q = map(int,input().split())
b = list()
for i in range(q):
    a = int(input())
    b.append(a)
for j in range(1,n+1):
    c = b.count(j)
    if c < q-k+1:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n, k, q = map(int,input().split())
a = []
for i in range(q):
    b = int(input())
    a.append(b)
pnt = [0] * n
for x in a:
    pnt[x-1] += 1
for j in range(n):
    if pnt[j] > q-k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
pgcd = True
sgcd = a[n-1]

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
if sgcd!=1:
    print('not coprime')
else:
    for i in range(0,n-1):
        sgcd = math.gcd(sgcd, a[i])    
        for j in range(i+1,n):
            if math.gcd(a[i], a[j]) != 1:
                print('setwise coprime')
                break
        else:
            continue
        break
    else:
        print('pairwise coprime')

### FIXED CODE ###

import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
NUM = 1_000_005
aa = [0]*NUM
pgcd = True
sgcd = a[n-1]
aa[a[n-1]]+=1
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    aa[a[i]]+=1

for i in range(2,NUM):
    tmp = sum(aa[i::i])
    if tmp >= 2:
        pgcd = False
        break
        
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

S = input()
Q = int(input())
Q_list = list()
for i in range(Q):
    Q_list.append(input().split())

def operate(i):
    global S_list, count
    if Q_list[i][0] == '1':
        count += 1
    else:
        if count % 2 == 0:
            if Q_list[i][1] == '1':
                S_list = [Q_list[i][2]] + S_list
            else:
                S_list = S_list + [Q_list[i][2]]
        else:
            if Q_list[i][1] == '1':
                S_list = S_list + [Q_list[i][2]]
            else:
                S_list = [Q_list[i][2]] + S_list
 
S_list = [i for i in S]
check = 0
for i in range(Q):
    if Q_list[i][0] == '1':
        check += 1
if check % 2 == 1:
    S_list = list(reversed(S_list))

count = check % 2
for i in range(Q):
    operate(i)
print(''.join(S_list))

### FIXED CODE ###

S = input()
Q = int(input())
Q_list = list()
for i in range(Q):
    Q_list.append(input().split())

from collections import deque
def operate(i):
    global count, str_list
    if Q_list[i][0] == '1':
        count += 1
    else:
        if count % 2 == 0:
            if Q_list[i][1] == '1':
                str_list.appendleft(Q_list[i][2])
            else:
                str_list.append(Q_list[i][2])
        else:
            if Q_list[i][1] == '1':
                str_list.append(Q_list[i][2])
            else:
                str_list.appendleft(Q_list[i][2])

check = 0
for i in range(Q):
    if Q_list[i][0] == '1':
        check += 1

S_list = [i for i in S]
if check % 2 == 1:
    S_list = list(reversed(S_list))

S_n = ''.join(S_list)

str_list = deque()
str_list.append(S_n)
count = check%2
for i in range(Q):
    operate(i)
print(''.join(str_list))
### BUGGY CODE ###

import itertools
k,s=map(int,input().split())

cnt=0
for x,y,z in itertools.product(range(k+1),range(k+1),range(k+1)):
  if x+y+z==s:
    cnt+=1
print(cnt)

### FIXED CODE ###

import itertools
k,s=map(int,input().split())

arr=[]
cnt=0

for x in range(k+1):
  for y in range(x,k+1):
    z=s-x-y
    if y<=z<=k:
      if x==y==z:
        cnt+=1
      elif x==y or y==z or z==x:
        cnt+=3
      else:
        cnt+=6
print(cnt)
### BUGGY CODE ###

x = int(input())
for i in range(1,x+1):
    if i%3 ==0 or i%10 ==3:
        print(' ',i,end='',sep='')
    else:
        while True:
            if x <= i:
                print()
                break

### FIXED CODE ###

A = int(input())
for i in range(3, A + 1):
    if i%3 == 0 or i%10 == 3 or '3' in str(i):
        print('', i , end = '')
print()
### BUGGY CODE ###

a,b,k = list(map(int, input().split()))
ans = range(a, b+1)
for i in ans:
    if a + k <= i <= b - k:
        continue
    print(i)

### FIXED CODE ###

a,b,k = list(map(int, input().split()))
ans = []
for i in range(k):
    n = a + i
    if n > b:
        break
    ans.append(n)

st = b - k + 1
st = max(st, ans[-1]+1)
for i in range(st, b+1):
    ans.append(i)

print(*ans, sep='\n')
### BUGGY CODE ###

import itertools
X=int(input())
ans=0

for i0,i1,i2,i3,i4,i5 in itertools.product(
    list(range(int(X//100)+1)),
    list(range(int(X//101)+1)),
    list(range(int(X//102)+1)),
    list(range(int(X//103)+1)),
    list(range(int(X//104)+1)),
    list(range(int(X//105)+1))):
    
    if (i0*100+i1*101+i2*102+i3*103+i4*104+i5*105)==X:
        ans=1
        break
if ans==1:
    print(str(1))
else:
    print(str(0))

### FIXED CODE ###

import sys
X=int(input())
for c in range(X):
    if (100*c<=X) and (105*c>=X):
        print(1)
        sys.exit()
print(0)
### BUGGY CODE ###

N,X,Y = list(map(int,input().split(' ')))
ls = {}
for i in range(1,N):
	for j in range(i+1,N+1):
		l = min(abs(j-i),abs(i-X)+1+abs(j-Y),abs(i-Y)+1+abs(j-X))
		if l not in ls.keys():
			ls[l] = 1
		else:
			ls[l] = ls[l] + 1

for i,(k,v) in enumerate(sorted(ls.items(),key=lambda x:x[0])):
	print(v)

for j in range(i+2,N):
	print(0)

### FIXED CODE ###

N,X,Y = list(map(int,input().split(' ')))

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

for i in range(1,N):
	for j in range(i+1,N+1):
		l = min(j-i,abs(i-X)+1+abs(j-Y))
		ls[l-1] = ls[l-1] + 1

for i in range(N-1):
	print(ls[i])
### BUGGY CODE ###

h,n = map(int,input().split())
spel = [list(map(int,input().split())) for i in range(n)]
dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(h):
  for damage,cost in spel:
    n_i = min(i+damage,h)
    dp[n_i] = min(dp[n_i],dp[i]+cost)
print(dp[h])

### FIXED CODE ###

h,n = map(int,input().split())
spel = [list(map(int,input().split())) for i in range(n)]
dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(h):
  for damage,cost in spel:
    n_i = min(i+damage,h)
    dp[n_i] = min(dp[n_i],dp[i]+cost)
print(dp[h])
### BUGGY CODE ###

n=int(input())
num=[i+1 for i in range(n)]
p=[i for i in range(2,n+1)]
p.append(1)
ans=0
for i in range(n):
    ans+=num[i]%p[i]

print(ans)

### FIXED CODE ###

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

N, K = list(map(int, input().split()))
H = sorted([int(input()) for _ in range(N)])

ans = float("inf")

for i in range(N-K+1):
    tree = H[i:i+K]
    ans =min(ans, max(tree)-min(tree))
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
H = [int(input()) for _ in range(N)]
H.sort()
ans = []

for i in range(N-K+1):
    ans.append(H[i+K-1]-H[i])
print(min(ans))
### BUGGY CODE ###

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

ac = 0
wa = 0
end = []

wa_candidate = [0 for i in range(N)]
for _ in range(M):
    p_i, s_i = input().split()
    if p_i not in end:
        if s_i == "AC":
            ac += 1
            wa += wa_candidate[int(p_i) - 1]
            end.append(p_i)
        if s_i == "WA":
            wa_candidate[int(p_i) - 1] += 1

print(ac, wa)

### FIXED CODE ###

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

ac = 0
wa = 0
ac_status = [0 for i in range(N)]
wa_status = [0 for i in range(N)]

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC" and ac_status[int(p_i) - 1] == 0:
        ac += 1
        ac_status[int(p_i) - 1] += 1
        wa += wa_status[int(p_i) - 1]
    if s_i == "WA":
        wa_status[int(p_i) - 1] += 1

print(ac, wa)
### BUGGY CODE ###

import functools
from fractions import gcd
k = int(input())
cnt = 0
for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            if i == j and j == l:
                cnt += i
            elif i == j and j != l:
                li = [i,l]
                cnt += functools.reduce(gcd,li)*3
            elif i != j and j == l:
                li = [i,j]
                cnt += functools.reduce(gcd,li)*3
            else:
                li = [i,j,l]
                cnt += functools.reduce(gcd,li)*6
print(cnt)

### FIXED CODE ###

import functools
from math import gcd
k = int(input())
cnt = 0
for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            if i == j and j == l:
                cnt += i
            elif i == j and j != l:
                li = [i,l]
                cnt += functools.reduce(gcd,li)*3
            elif i != j and j == l:
                li = [i,j]
                cnt += functools.reduce(gcd,li)*3
            else:
                li = [i,j,l]
                cnt += functools.reduce(gcd,li)*6
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

cnt = 0
t = []
for a,b in tmp:
    t=t+[b]*a
    cnt+= a
    if cnt >=N:
        break

A = A + t
A.sort(reverse = 1)
print(sum(A[:N]))



### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

if __name__ == '__main__':
    sol()