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

import math

def permutations_count(n, r):
    if (n < 2):
        return 0
    else:
        return math.factorial(n) // math.factorial(n - r)

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

bar = {}

for i in range(N):
    if (A[i] in bar):
        bar[A[i]] = bar[A[i]] + 1
    else:
        bar[A[i]] = 1

partOfNum = {}

for j in bar.keys():
    tmp = permutations_count(bar[j], 2)
    partOfNum[j] = int(tmp / 2)

for i in range(N):
    jogai = A[i]
    seed = bar[jogai] - 1
    tmp2 = permutations_count(seed, 2)
    lackCombination = int(tmp2 / 2)
    for k in partOfNum.keys():
        if (k != jogai):
            lackCombination += partOfNum[k]
    print(lackCombination)


### FIXED CODE ###

import math

def permutations_count(n, r):
    if (n < 2):
        return 0
    else:
        return math.factorial(n) // math.factorial(n - r)

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

bar = {}

for i in range(N):
    if (A[i] in bar):
        bar[A[i]] = bar[A[i]] + 1
    else:
        bar[A[i]] = 1

partOfNum = {}
lackPartOfNum = {}

for j in bar.keys():
    tmp = permutations_count(bar[j], 2)
    partOfNum[j] = int(tmp / 2)
#   tmp = permutations_count(bar[j] - 1, 2)
    lackPartOfNum[j] = partOfNum[j] - (bar[j] - 1)

allSum = 0
for l in partOfNum.keys():
    allSum += partOfNum[l]

for i in range(N):
    print(allSum - partOfNum[A[i]] + lackPartOfNum[A[i]])
### BUGGY CODE ###

A,B = (int(i) for i in input().split())

if B == 1:
    print(0)

else:
    ans = 1
    while 1:
        if A + (A-1) * (ans - 1) >= B:
            break
            ans += 1

    print(ans)


### FIXED CODE ###

A,B = (int(i) for i in input().split())

if B == 1:
    print(0)

else:
    ans = 1
    while 1:
        if A + (A-1) * (ans - 1) >= B:
            break
        ans += 1

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

s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列
dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + s[i]
    else:
      if len(dp[i+1][j])>len(dp[i][j+1]):
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
print(dp[len(s)][len(t)])


### FIXED CODE ###

s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列長
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      if dp[i+1][j] > dp[i][j+1]:
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
#print(dp)
#print(dp[len(s)][len(t)])

# dpを逆にたどって最長部分文字列を復元する
ans = ''
i = len(s)
j = len(t)
while(dp[i][j]>0):
  if dp[i][j] == dp[i-1][j-1] +1 and dp[i][j] == dp[i-1][j] +1 and dp[i][j] == dp[i][j-1] +1:
    ans += s[i-1]
    i -= 1
    j -= 1
  elif dp[i-1][j] > dp[i][j-1]:
    i -= 1
  else:
    j -= 1
print(''.join(reversed(list(ans))))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
mod = 10**9+7
bouquet = 0
n,a,b = map(int,input().split())
for i in range(1,n+1):
    if i != a and i != b:
        bouquet += cmb(n,i) % mod
        bouquet = bouquet % mod
print(bouquet % mod)

### FIXED CODE ###

def pow(a,b,c):
    ans = 1
    while b > 0:
        if b & 1:
            ans = ans*a % c
        a = a*a % c
        b = b >> 1
    return ans
def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(n-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num*pow(den,c-2,c) % c
mod = 10**9+7
n,a,b = map(int,input().split())
ans  = (pow(2,n,mod)-cmb(n,a,mod)-cmb(n,b,mod)-1) % mod
if ans < 0:
    ans = ans + mod
print(ans)
### BUGGY CODE ###

import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
d.sort(reverse = True)
for i in range(k):
    if d[0][2] > 0:
        d[0][0] -= d[0][1]
        d[0][2] -= 1
        d.sort(reverse = True)
    else:
        break
print(d[0][0])

### FIXED CODE ###

def main():

    import numpy as np
    
    n, k = map(int, input().split())
    a = np.array(input().split(), np.int64)
    f = np.array(input().split(), np.int64)
    a.sort()
    a = a[::-1]
    f.sort()
    right = np.max(a*f)
    left = 0
    while right > left:
        middle = (right + left)//2
        b = 0
        
        if np.sum(np.maximum(a-middle//f, 0)) <= k:
            right = middle
        else:
            left = middle+1

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

import collections
import sys

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


if d[0]!=0:
    print(0)
    sys.exit(0)

p=1

for i in range(1,max(d)+1):
        p = (p * pow(d.count(i-1), d.count(i), 998244353))%998244353

print(p)

### FIXED CODE ###

import collections
import sys

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

cnt = collections.Counter(d)

if d[0]!=0:
    print(0)
    sys.exit(0)

if cnt[0]!=1:
    print(0)
    sys.exit(0)    
    
p = 1

for i in range(1,max(d)+1):
    if cnt[i] == 0:
        print(0)
        sys.exit(0)  
    else:
        p = (p * pow(cnt[i-1], cnt[i], 998244353))%998244353

print(p)
### BUGGY CODE ###

import itertools
N = int(input())

cnt = 0
L = list(range(1, N))
for i in itertools.product(L, repeat=3):
    if (i[0]*i[1])+i[2] == N:
        cnt += 1

print(cnt)

### FIXED CODE ###

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

# problem a
# score 300
from collections import defaultdict
N = int(input())
A = []
from decimal import Decimal
for i in range(N):
    x = float(input())
    x = Decimal(x*(10**9))
    A.append(x)
remove = 0
for i in range(N):
    if (A[i]**2) % (10**18) == 0:
        remove += 1
D = defaultdict(int)
data = []
for x in A:
    order2 = 0
    order5 = 0
    K = x
    while K % 2 == 0:
        order2 += 1
        K = K//2
    while K % 5 == 0:
        order5 += 1
        K = K//5
    data.append((order2, order5))
    for i in range(order2+1):
        for j in range(order5+1):
            D[2**i*5**j] += 1
ans = 0
for ord2, ord5 in data:
    new_ord2 = max(0, 18-ord2)
    new_ord5 = max(0, 18-ord5)
    ans += D[(2**new_ord2)*(5**new_ord5)]
ans-=remove
ans = ans//2
print(ans)

### FIXED CODE ###

# problem a
# score 300
from collections import defaultdict
N = int(input())
A = []
for i in range(N):
    x = float(input())
    x = "{:.9f}".format(x)
    x=int(x[:-10]+x[-9:])
    A.append(x)
remove = 0
for i in range(N):
    if (A[i]**2) % (10**18) == 0:
        remove += 1
D = defaultdict(int)
data = []
for x in A:
    order2 = 0
    order5 = 0
    K = x
    while K % 2 == 0:
        order2 += 1
        K = K//2
    while K % 5 == 0:
        order5 += 1
        K = K//5
    data.append((order2, order5))
    for i in range(order2+1):
        for j in range(order5+1):
            D[2**i*5**j] += 1
ans = 0
for ord2, ord5 in data:
    new_ord2 = max(0, 18-ord2)
    new_ord5 = max(0, 18-ord5)
    ans += D[(2**new_ord2)*(5**new_ord5)]
ans-=remove
ans = ans//2
print(ans)
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = []
for _ in range(M):
  B,C = map(int,input().split())
  BC.append([B,C])
BC.sort(key=lambda x: x[1], reverse=True)
for i in BC:
  b,c = i[0],i[1]
  index = bisect.bisect_left(A,c)
  index = min(index,b)
  if index==0:
    continue
  A = [c for _ in range(index)] + A[index:]
  A.sort()
print(sum(A))

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
D = []
for _ in range(M):
  D.append(list(map(int,input().split())))
D.sort(key=lambda x:x[1], reverse=True)
cnt = 0
ans = []
for d in D:
  b,c = d[0],d[1]
  ans += [c for _ in range(b)]
  cnt += b
  if cnt>=N:
    break
ans = ans[:min(cnt,N)] + A
ans.sort(reverse=True)
print(sum(ans[:N]))
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
B = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    A.append(x1)
    B.append(y1)
    
yen = 0
num = 0
while num < M:
    a  = min(A)
    ind = A.index(a)
    
    if num + B[ind] <= M:
        yen += a * B[ind]
        num += B[ind]
        del A[ind]
        del B[ind]
    else:
        yen += a * (M - num)
        break
print(yen)

### FIXED CODE ###

N, M = map(int, input().split())
S = []
C = 0
cost = 0
for i in range(N):
  a, b = map(int, input().split()) 
  S.append((a, b))
S.sort()
for i in range(N):
  if S[i][1] + C < M:
    C += S[i][1]
    cost += S[i][0] * S[i][1]
  else:
    cost += (M-C) * S[i][0]
    break
print(cost)
### BUGGY CODE ###

N, A, B = map(int, input().split())
ans = 0
cnt = 0
while True:
    cnt += A
    ans += A
    if cnt >= N:
        ans -= cnt - N
        break
    cnt += B
    if cnt >= N:
        break
print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
ab = A + B
cnt = N // ab
remain = N - (cnt * ab)
blue = 0
if remain > A:
    blue = A
else:
    blue = remain
ans = A * cnt + blue
print(ans)
### BUGGY CODE ###

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = [list(map(int,input().split())) for _ in [0]*N]
XYR.append([xs,ys,0])
XYR.append([xt,yt,0])

E = [{} for _ in [0]*(N+2)]
for i in range(N+2):
    for j in range(N+2):
        if j==i : continue
        dx = XYR[i][0]-XYR[j][0]
        dy = XYR[i][1]-XYR[j][1]
        r2 = XYR[i][2]+XYR[j][2]
        E[i][j] = max(0,(dx**2+dy**2)**0.5 - r2)

import heapq
def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

print(Dijkstra(N+2,E,N)[-1])

### FIXED CODE ###

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = [list(map(int,input().split())) for _ in [0]*N]
XYR.append([xs,ys,0])
XYR.append([xt,yt,0])

E = [{} for _ in [0]*(N+2)]
for i in range(N+2):
    for j in range(N+2):
        if j==i : continue
        dx = XYR[i][0]-XYR[j][0]
        dy = XYR[i][1]-XYR[j][1]
        r2 = XYR[i][2]+XYR[j][2]
        E[i][j] = max(0,(dx**2+dy**2)**0.5 - r2)

import heapq
def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

print(Dijkstra(N+2,E,N)[-1])
### BUGGY CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m%mod
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()


### FIXED CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


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

n = int(input())
list = input().split()
 
int_list = [ int(n) for n in list ]
 
isDist = True
 
for a in range(n):
  if int_list.count(int_list[a]) != 1:
    print("NO")
    isDist = False
    break;
 
if isDist is True:
    print("YES")

### FIXED CODE ###

n = int(input())
list = input().split()
 
int_list = [ int(n) for n in list ]
int_list.sort()

isDist = True
 
for a in range(n-1):
  if int_list[a] == int_list[a+1]:
    print("NO")
    isDist = False
    break;
 
if isDist is True:
    print("YES")
### BUGGY CODE ###

S = input()
num = 0
for i in list(range(0,len(S))):
    for j in list(range(i, len(S))):
        suuji = int(S[i:j+1])
        if suuji % 2019==0:
            num += 1
print(num)




### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i] * A[j]
    ans = ans % 1000000007
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
a = 0
b = 0
mod = 10**9 + 7
for i in range(N):
    a += A[i]
    b += A[i]**2
    a = a 
    b = b 
a = a ** 2 
ans = (a - b) // 2 % mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
d=[[]for i in range(b+1)]
for i in c:
  if i[0]<=b:
    e=i[0]
    d[e].append(i[1])
    
for i in range(b+1):
  d[i].sort()
sum=0
for i in range(b+1):
  e=0
  f=0
  for j in range(i+1):
    if len(d[j])!=0:
      if e<=d[j][-1]:
        f=j
        e=d[j][-1]    
  sum+=e
  if f>0:
    d[f].pop()
      
    
  
print(sum)

### FIXED CODE ###

import heapq
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
c.sort()
d=[[0]for i in range(b)]
sum=0
for i,j in c:
  if i<=b:
    d[i-1].append(j)
e=[]

for i in d:
  for j in i:
    heapq.heappush(e,-j)
  sum-=heapq.heappop(e)
      
    
  
print(sum)
### BUGGY CODE ###

import itertools
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    p1,c1=map(int,input().split())
    p.append(p1)
    c.append(c1//100)
n=list(itertools.permutations(list(range(1,d+1))))
ans=1100
g//=100
for i in range(len(n)):
    cnt=g
    cnt2=0
    for j in range(d):
        num3=n[i][j]
        num4=num3*p[num3-1]
        if num4>=cnt:
            cnt2+=((cnt-1)//num3)+1
            break
        elif num4+c[num3-1]>=cnt:
            cnt2+=p[num3-1]
            break
        else:
            cnt-=num4+c[num3-1]
            cnt2+=p[num3-1]
    ans=min(ans,cnt2)
print(ans)


### FIXED CODE ###

import itertools
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    p1,c1=map(int,input().split())
    p.append(p1)
    c.append(c1//100)
n=list(itertools.permutations(list(range(1,d+1))))
ans=1024
g//=100
for i in range(len(n)):
    cnt=g
    cnt2=0
    for j in range(d):
        num3=n[i][j]
        num4=num3*p[num3-1]
        if num4>=cnt:
            cnt2+=((cnt-1)//num3)+1
            break
        elif num4+c[num3-1]>=cnt:
            cnt2+=p[num3-1]
            break
        else:
            cnt-=num4+c[num3-1]
            cnt2+=p[num3-1]
    ans=min(ans,cnt2)
print(ans)
### BUGGY CODE ###

N=int(input())
l=list(map(int,input().split()))
l.sort()
count=0

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if l[i]+l[j]>l[k]:
                count+=1
print(count)

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
l.sort()
count=0
import bisect
for i in range(N):
    for j in range(i+1,N-1):
        m=bisect.bisect_left(l,l[i]+l[j])
        count+=m-(j+1)
print(count)
### BUGGY CODE ###

def main():
    strings = input().split(' ')
    N = int(strings[0])
    K = int(strings[1])
    p_raw = input().split(' ')
    exp = []
    for i in p_raw:
        exp.append((int(i)+1)/2.)
    max = 0
    for i in range(N-K+1):
        
        sum_exp = sum(exp[i:i+K])
        if sum_exp > max:
            max = sum_exp
            
    
    print(max)
    return 0

main()

### FIXED CODE ###

def main():
    strings = input().split(' ')
    N = int(strings[0])
    K = int(strings[1])
    p_raw = input().split(' ')
    exp = []
    for i in p_raw:
        exp.append((int(i)+1)/2.)
    max = 0
    exp_prev = sum(exp[0:0 + K -1])
    for i in range(N-K+1):
        
        sum_exp = exp_prev + exp[i + K-1]
        exp_prev = sum_exp - exp[i]
        if sum_exp > max:
            max = sum_exp
            
    
    print(max)
    return 0

main()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    B.append(A[i])
    B=B[::-1]
print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
answer = A[1::2][::-1]+A[::2]
if n%2==1:
    answer=answer[::-1]
print(*answer)
### BUGGY CODE ###

n = int(input())
dictionary = []

for _ in range(n):
    cmd, arg = input().split()
    if cmd == "insert":
        dictionary.append(arg)
    elif cmd == "find":
        if arg in dictionary:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

n = int(input())
dictionary = set()

for _ in range(n):
    cmd, arg = input().split()
    if cmd == "insert":
        dictionary.add(arg)
    elif cmd == "find":
        if arg in dictionary:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))
ans = 0

for n in range(N-K+1):
	#tmp = sum(list(map(lambda x: (x+1)/2, p[n:n+K])))
	tmp = np.sum((p[n:n+K]+1)/2)
	if ans < tmp:
		ans = tmp

print(ans)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))
ans = tmp = np.sum((p[0:K]+1)/2)

for n in range(1, N-K+1):
	last = (p[n-1]+1)/2
	next = (p[n+K-1]+1)/2
	tmp = tmp - last + next
	if ans < tmp:
		ans = tmp

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

import sys

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    TO_K[child] = TO_K[parent] + DISTANCE[parent][child]

    for i_gch in TREE[child]:
        if i_gch == parent:
            continue
        dfs(i_gch, child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    global DISTANCE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    DISTANCE = [[0]*(n+1) for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append(b)
        TREE[b].append(a)
        DISTANCE[a][b] = c
        DISTANCE[b][a] = c

    dfs(k, 0)

    for x, y in xy:
        print(TO_K[x]+TO_K[y])
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

TO_K = []
TREE = []

def dfs(parent, distance):
    for i_node in TREE[parent]:
        child, dd = i_node
        if TO_K[child] != -1:
            continue

        next_dt = distance + dd
        TO_K[child] = next_dt
        dfs(child, next_dt)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [-1]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    TO_K[k] = 0
    dfs(k, 0)

    for x, y in xy:
        print(TO_K[x]+TO_K[y])
    return


if __name__ == "__main__":
    main()
    sys.exit(0)
### BUGGY CODE ###

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

if K == 1:
    print(0)

elif N == K:
    print(0)

elif N == 0:
    print(0)

elif N % 2 == 0 and K % 2 == 0 and N > K and K % N == 0:
    print(0)
elif N % 2 == 0 and K % 2 == 0 and N > K and K % N != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10 ** 18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break


elif N % 2 == 0 and K % 2 == 0 and N < K and K % N == 0:
    print(N)
elif N % 2 == 0 and K % 2 == 0 and N < K and K % N != 0:
    if abs(N - K) > N:
        print(N)
    else:
        print(abs(N - K))


elif N % 2 == 1 and K % 2 == 1 and N > K and K % N == 0:
    print(0)
elif N % 2 == 1 and K % 2 == 1 and N > K and K % N != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10**18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break


elif N % 2 == 0 and K % 2 == 0 and N < K and K % N == 0:
    print(N)
elif N % 2 == 0 and K % 2 == 0 and N < K and K % N != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10 ** 18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break


elif N % 2 == 0 and K % 2 == 1 and N > K and N % K != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10 ** 18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break
elif N % 2 == 0 and K % 2 == 1 and N > K and N % K == 0:
    print(0)


elif N % 2 == 0 and K % 2 == 1 and N < K and N % K != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10 ** 18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break
elif N % 2 == 0 and K % 2 == 1 and N < K and N % K == 0:
    print(0)


elif N % 2 == 1 and K % 2 == 0 and N > K and N % K != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10 ** 18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break
elif N % 2 == 1 and K % 2 == 0 and N > K and N % K == 0:
    print(0)


elif N % 2 == 1 and K % 2 == 0 and N < K and N % K != 0:
    if abs(N - K) > N:
        print(N)
    else:
        for i in range(10 ** 18):
            if N > abs(N - K):
                N = abs(N - K)
            else:
                print(N)
                break
elif N % 2 == 1 and K % 2 == 0 and N < K and N % K == 0:
    print(N)

else:
    print("NG")



### FIXED CODE ###

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

print(min(N % K, abs(K - N % K)))
### BUGGY CODE ###

n, q = [int(x) for x in input().split()]
s = input()

for i in range(q):
    l, r = [int(x) for x in input().split()]
    t = s[l-1:r]
    print(t.count('AC'))


### FIXED CODE ###

import bisect

n, q = [int(x) for x in input().split()]
s = input()

index = []
for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        index.append(i)

for i in range(q):
    l, r = [int(x) for x in input().split()]
    print(bisect.bisect_right(index, r-2) - bisect.bisect_left(index, l-1))
### BUGGY CODE ###

N,M = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
B = [0]*M
for j in range(M):
	B[j] = list(map(int,input().split(" ")))

tmp = sorted(B,key=lambda x:x[1],reverse=True)
A.sort()

r = 0
for i in tmp:
	for k in range(r,N,1):
		if i[1] > A[k] and i[0] > 0:
			A[k] = i[1]
			i[0] -= 1
			r = k

print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
B = [0]*M
for j in range(M):
	B[j] = list(map(int,input().split(" ")))

tmp = sorted(B,key=lambda x:x[1],reverse=True)
A.sort()

r = 0
for i in tmp:
	for k in range(r,N,1):
		if i[1] > A[k] and i[0] > 0:
			A[k] = i[1]
			i[0] -= 1
			r = k+1
		elif A[k] > i[1] or i[0] == 0:
			break

print(sum(A))