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

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


### FIXED CODE ###

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

X = dict()
ans = 0
for i in range(N):
    L = i + A[i]
    if L not in X:
        X[L] = 1
    else:
        X[L] += 1

for i in range(N):
    R = i - A[i]
    if R in X:
        ans += X[R]
        
print(ans)
### BUGGY CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [0 for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]

    def add_p(num):
        if visit[num] == 1:
            return 0
        visit[num] = 1
        for i in dic[num]:
            if visit[i] == 0:
                point[i] += point[num]
                add_p(i)
        return 0

    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x

    add_p(0)

    print(" ".join(map(str, point)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
import bisect

def is_like_2017(num):
  if all([is_prime(num), is_prime(int((num+1)/2))]): return True
  else: return False
  
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

def get_prime_nums(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  return nums

prime_nums = list(get_prime_nums(10**5))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(prime_nums, l)
  idx_r = bisect.bisect_right(prime_nums, r)
 
  ans = 0
  for i in range(idx_l, idx_r):
    if is_like_2017(prime_nums[i]) is True:ans += 1
  print(ans)
    

### FIXED CODE ###

import math
import bisect
  
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

def get_like_2017(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  
  nums_like_2017 = set([])
  for num in nums:
    if is_prime(int((num+1)/2)) is True:  nums_like_2017.add(num)
  return nums_like_2017

nums_like_2017 = sorted(list(get_like_2017(10**5)))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(nums_like_2017, l)
  idx_r = bisect.bisect_right(nums_like_2017, r)
 
  print(idx_r-idx_l)
### BUGGY CODE ###

h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;t=j=w;r,*d=[0]*w
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j,i=j,j+(t>j),h
 m+=r+c,
print(min(m))

### FIXED CODE ###

h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)
### BUGGY CODE ###

import collections
N = int(input())
lis = []
ans = 0

for i in range(N):
    lis.append("".join(sorted(input())))

for i in set(lis): 
    n = lis.count(i) - 1
    ans += int(0.5*n*(n+1))
print(ans)

### FIXED CODE ###

import collections
N = int(input())
l = []
ans = 0

for i in range(N):
    l.append("".join(sorted(input())))

for v in (collections.Counter(l)).values():
    v -= 1
    ans += int(0.5*v*(v+1))

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

import numpy as np

def f(s):
    k = len(s)
    md = 10 ** 9 + 7
    dp = np.zeros((k + 1, 13), dtype="i8")
    dp[0][0] = 1
    for i, c in enumerate(s[::-1]):
        if c == "?":
            for n in range(10):
                m = n * 10 ** i % 13
                dp[i + 1][:m] = (dp[i + 1][:m] + dp[i][13 - m:]) % md
                dp[i + 1][m:] = (dp[i + 1][m:] + dp[i][:13 - m]) % md
        else:
            m = int(c) * 10 ** i % 13
            dp[i + 1][:m] = (dp[i + 1][:m] + dp[i][13 - m:]) % md
            dp[i + 1][m:] = (dp[i + 1][m:] + dp[i][:13 - m]) % md
    print(dp[k][5])

s = input()
f(s)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

def main():
    s = SI()
    n = len(s)
    dp = [[0] * 13 for _ in range(n + 1)]
    # dp[i][m]...iケタ目までみたときに、余りがmになる数の個数
    dp[0][0] = mint(1)
    e10 = 1
    for i, c in enumerate(s[::-1]):
        for m in range(13):
            pre = dp[i][m]
            if pre == 0: continue
            if c == "?":
                for d in range(10):
                    nm = (m + d * e10) % 13
                    dp[i + 1][nm] += pre
            else:
                nm = (m + int(c) * e10) % 13
                dp[i + 1][nm] += pre
        e10 = e10 * 10 % 13
    print(dp[n][5])

main()
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)

Pair=[0 for i in range(N)]
for i in range(N-1):
    Pair[i]=A[i]+A[i+1]

ans=0
cnt=0
mode=0
Next=[]
i=0
while i<M:
    if mode==0:
        ans+=2*A[cnt]
        mode=1
        Next.append([cnt,cnt+1])
        cnt+=1
        i+=1
    else:
        Max=0
        for j in Next:
            if Max<=A[j[0]]+A[j[1]]:
                Max=A[j[0]]+A[j[1]]
                p_cnt=j
        ans+=A[p_cnt[0]]+A[p_cnt[1]]
        i+=1
        
        if i<=M-1:
            ans+=A[p_cnt[0]]+A[p_cnt[1]]
            i+=1
        Next.remove(p_cnt)
        if p_cnt[1]+1<N:
            p_cnt[1]+=1
            Next.append(p_cnt)
            
        Max=max(Max,A[p_cnt[0]]+A[p_cnt[1]])
        if Max<=A[cnt]*2 or Next==[]:
            mode=0
        
print(ans)

### FIXED CODE ###

#E
from bisect import bisect_left
from itertools import accumulate

N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
A_r=list(reversed(A))
B=[0]+list(accumulate(A_r))

def f(x):
    count=0
    for i in A:
        idx=bisect_left(A,x-i)
        count+=N-idx
    if count>=M:
        return True
    else:
        return False
    
MIN=0
MAX=2*10**5+1
while MAX-MIN>1:
    MID=(MIN+MAX)//2
    if f(MID):
        MIN=MID
    else:
        MAX=MID

ans=0
count=0
for i in A_r:
    idx=bisect_left(A,MIN-i)
    ans+=i*(N-idx)+B[N-idx]
    count+=N-idx
print(ans-(count-M)*MIN)
### BUGGY CODE ###

n=int(input())
A = [0]*(n)
for i in range(n):
    s=int(input())
    A[i]=s
    
lista=sorted(A)
cnt=0
for a in range(0,n,2):
    if A.index(lista[a])%2!=0:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
A = [0]*(n)
for i in range(n):
    s=int(input())
    A[i]=[s,i]    
lista=sorted(A,key=lambda x:x[0])
cnt=0
for i in range(n):
    lista[i].append(i)
for i in range(n):
    if (lista[i][1]-lista[i][2])%2!=0:
        cnt+=1
print(cnt//2)
### BUGGY CODE ###

quest = []
N, Q = input().split()
N = int(N)
Q = int(Q)
S = input()
for _ in range(Q):
    tmp = []
    s, e = input().split()
    tmp.append(int(s))
    tmp.append(int(e))
    quest.append(tmp)

# for i in range(Q):
#     print(S.count('AC', quest[i][0]-1, quest[i][1]))
for i in range(Q):
    cnt = 0
    cc = 0
    for j in S[quest[i][0]-1: quest[i][1]]:
        if j != 'A' and j != 'C':
            continue
        elif j == 'A':
            cc = 1
        elif j == 'C' and cc == 1:
            cnt += 1
            cc = 0
    print(cnt)



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
ans = [0]*(N+1)
for i in range(N):
    ans[i+1] = ans[i]
    if S[i: i+2] == 'AC':
        ans[i+1] += 1
for _ in range(Q):
    start, end = map(int, input().split())
    cnt = ans[end-1] - ans[start-1]
    print(cnt)
### BUGGY CODE ###

import math

def nPr(n, r):
    return math.factorial(n) // math.factorial(n - r)



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

ab = []
dic = {}
ans = 1

for i in range(N-1):

    a,b = map(int,input().split())
    ab.append([a,b])


while True:

    #print (ab)

    dic = {}

    if len(ab) == 0:
        ans *= K
        break
    elif len(ab) == 1:
        ans *= K * (K-1)
        break

    for i in ab:
        
        if i[0] in dic:
            dic[i[0]].append(i[1])
        
        else:
            dic[i[0]] = [i[1]]

        if i[1] in dic:
            dic[i[1]].append(i[0])
        
        else:
            dic[i[1]] = [i[0]]

    
    miki = []
    lma = 0
    for i in dic:

        lma = max(len(dic[i]),lma)
        if len(dic[i])>=2:
            miki.append(i)

    if lma >= K:
        ans = 0
        break

    for i in miki:

        lin_mik = 0
        for j in dic[i]:

            if j in miki:
                lin_mik += 1

        ans *= nPr( K - (1 + lin_mik) , len(dic[i])-lin_mik )
        #print (i,"のまわりは",nPr( K - (1 + lin_mik) , len(dic[i])-lin_mik ),"とおり")

    nab = []
    for i in ab:

        if (i[0] in miki) and (i[1] in miki):

            nab.append(i)

    ab = nab.copy()
    #print (miki,"みき",ans)

print (ans % (1000000007))


### FIXED CODE ###

from collections import deque
import sys

#modの掛け算

def modmal(a,b,mod): #a*bをmodを法にして求める

    return a * b % mod


#modの割り算

def moddiv(a,b,mod): #a/bをmodを法にして求める

    return (a * pow(b,mod-2,mod)) % mod


#逆元

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod



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

mod = 10**9+7
fac,inv = modfac(max(N,K)+100 , mod)

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

ans = K

for i in dic:

    if i == 0:

        ans *= fac[K-1] * inv[K-len(dic[i])-1]
        ans %= mod

        if len(dic[i]) >= K:
            print (0)
            sys.exit()

    else:

        ans *= fac[K-2] * inv[K-len(dic[i])-1]
        ans %= mod

        if len(dic[i]) >= K:
            print (0)
            sys.exit()

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

N=int(input())
S=input()
count=0
r=[]
g=[]
b=[]
for i in range(N):
	if S[i]=="R":
		r.append(i+1)
	if S[i]=="G":
		g.append(i+1)
	if S[i]=="B":
		b.append(i+1)
for x in r:
	for y in g:
		for z in b:
			L=[x,y,z]
			#print(L)
			L=sorted(L)
			if (L[1]-L[0])!=(L[2]-L[1]):
				count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=input()
count=0
r=S.count("R")
g=S.count("G")
b=S.count("B")

count+=r*g*b
#print(r,g,b)
for i in range(0,N-1):
	for j in range(i+1,N):
		k=2*j-i
		if k>=N:break
		if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k]:
			count-=1
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10**18
AB = [A, B]

dp = [[INF] * 51 for _ in range(1 << N)]
dp[0][0] = 0

for state in range(1 << N):
    size = 0
    for i in range(N):
        if (state & (1 << i)) > 0:
            size += 1

    S = []
    now = size
    for i in range(N):
        if (state & (1 << i)) == 0:
            S.append((i, now))
            now += 1

    for s in range(51):
        for i, now in S:
            val = AB[(i - size) % 2][i]
            d = dp[state][s] + abs(now - size)
            if val >= s and dp[state | (1 << i)][val] > d:
                dp[state | (1 << i)][val] = d

ans = min(dp[(1 << N) - 1])
print(ans if ans < INF else -1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

print(ans if ans != INF else -1)
### BUGGY CODE ###

def main():

    import numpy as np

    N,K = map(int,input().split())
    A = np.array(list(map(int,input().split())))
    for _ in range(K):
        B = np.zeros(N,dtype=np.int64)
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l] += 1
            if N > r+1:
                B[r+1] -= 1
       
        A = np.cumsum(B)
        if np.all(B==N):
            break

    print(*A)

main()

### FIXED CODE ###

import numpy as np

from numba import njit
@njit(cache=True)
def solve(N,K,A):
    for _ in range(K):
        B = np.zeros(N,dtype=np.int64)
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l] += 1
            if N > r+1:
                B[r+1] -= 1
        
        A = np.cumsum(B)
        if np.all(A==N):
            break

    return A

def main():
    N,K = map(int,input().split())
    A = np.array(list(map(int,input().split())))

    A = solve(N,K,A)
    print(*A)

main()
### BUGGY CODE ###

N = int(input())
X = [int(x) for x in input().split(' ')]

for i in range(N):
    tmp = X[:i]
    tmp.extend(X[i+1:])
    tmp.sort()
    print(tmp[int((N-1) / 2)])

### FIXED CODE ###

N = int(input())
x = [int(x) for x in input().split()]
y = sorted(x)
l = y[len(x)//2-1]
r = y[len(x)//2]

for xi in x:
    if xi < r: print(r)
    else: print(l)
### BUGGY CODE ###

N = int(input())

C = 0
for i in range(1,10):
  for j in range(1,10):
    cij = 0
    cji = 0
    for k in range(1,N+1):
      s = str(k)
      if int(s[0]) == i and int(s[-1]) == j:
        cij += 1
      if int(s[0]) == j and int(s[-1]) == i:
        cji += 1
    C += cij*cji
print(C)


### FIXED CODE ###

import numpy as np
N = int(input())

def f(x):
  a = x%10
  b = 0
  while x > 0:
    b = x
    x //= 10
  return a,b

freq = np.zeros((10,10), dtype=int)
for k in range(1,N+1):
  a,b = f(k)
  freq[a,b] += 1

print((freq*freq.T).sum())
### BUGGY CODE ###

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

cnt = 0

table = [None]*N

for i in range(N):
    for j in range(i):
        if A[i] == table[j]:
            cnt += 1
        table[j] += 1
    
    table[i] = (-1)*A[i] + 1
    
print(cnt)

### FIXED CODE ###

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

P = [None]*N
M = [None]*N

for i in range(N):
    P[i] = i + A[i]
    M[i] = i - A[i]

P.sort() 
M.sort()

P_ = []
M_ = []

for i in range(N):
    if i == 0 or P[i] != P[i-1]:
        ele = [P[i], 1]
    else:
        ele[1] += 1
    if i == N-1 or P[i] != P[i+1]:
        P_.append(ele)
        
for i in range(N):
    if i == 0 or M[i] != M[i-1]:
        ele = [M[i], 1]
    else:
        ele[1] += 1
    if i == N-1 or M[i] != M[i+1]:
        M_.append(ele)
        

cnt = 0
lp = len(P_)
lm = len(M_)
for i in range(lp):
    idx = P_[i][0]
    head = 0
    tail = lm
    while tail - head > 1:
        center = (tail + head)//2
        if idx > M_[center][0]:
            head = center
        elif idx < M_[center][0]:
            tail = center
        else:
            cnt += P_[i][1] * M_[center][1]
            break
            
print(cnt)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
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 STR(): return input()
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 = sys.maxsize
mod = 10 ** 9 + 7

n, a, b = MAP()
h = [INT() for _ in range(n)]
ad = a - b
l = 1
r = 10 ** 9
while r - l > 1:
    c = (r + l) // 2
    hh = deepcopy(h)
    cnt = 0
    for i in range(n):
        hh[i] = max(hh[i] - b * c, 0)
        cnt += (hh[i] + ad - 1) // ad
    if c > cnt:
        r = c
    else:
        l = c
ans = inf
for i in range(max(0, l - 1000), r + 1000):
    hh = deepcopy(h)
    cnt = 0
    for j in range(n):
        hh[j] = max(hh[j] - b * i, 0)
        cnt += (hh[j] + ad - 1) // ad
    ans = min(ans, max(i, cnt))
print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
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 STR(): return input()
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 = sys.maxsize
mod = 10 ** 9 + 7

n, a, b = MAP()
h = [INT() for _ in range(n)]
ad = a - b
l = 1
r = 10 ** 9
while r - l > 1:
    c = (r + l) // 2
    cnt = 0
    for i in range(n):
        cnt += (max(h[i] - b * c, 0) + ad - 1) // ad
    if c > cnt:
        r = c
    else:
        l = c
ans = inf
for i in range(l, r + 1):
    cnt = 0
    for j in range(n):
        cnt += (max(h[j] - b * i, 0) + ad - 1) // ad
    ans = min(ans, max(i, cnt))
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        a.append(c)

s = sorted(a, reverse=True)
print(sum(s[:n]))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()])
heapq.heapify(a)
l = []

for _ in range(m):
    b, c = map(int, input().split())
    l.append((b, c))

l = sorted(l, key=lambda x: x[1], reverse=True)

for b, c in l:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] < c:
            heapq.heappushpop(a, c)
        else:
            break

print(sum(a))
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}

    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        key = '{}-{}-{}'.format(i,j,k)
        if key in dic:
            return dic[key]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        return ans

    ans = exp(a.count(1),a.count(2),a.count(3))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

n=int(input())
a=[input() for i in range(n)]
cnt=0
for i in set(a):
  _cnt = a.count(i)
  if _cnt>=2:
    cnt+=int(_cnt/2)
print(n-cnt*2)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=[input() for _ in range(n)]
cnt=Counter(a)
ans=0
for i in cnt.values():
  if i%2:
    ans+=1
print(ans)