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

n=int(input())
if n==1:
    print(1)
else:
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    ll=[]
    for i in range(n):
        flag=True
        for j in ll:
            if not l[i]%j:
                flag=False
                break
        if flag:
            ll.append(l[i])
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
    print(res)



### FIXED CODE ###

n=int(input())
if n==1:
    print(1)
else:
    oklist=[True for i in range(1000001)]
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    for i in range(n):
        if oklist[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(1,1000001):
                if l[i]*j<=1000000:
                    oklist[l[i]*j]=False
                else:
                  break
    print(res)
### BUGGY CODE ###

from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = int(arr, 2) % (cnt - 1)

ALL_ARR = int(arr, 2)

li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - (1 << (n - i - 1))) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

print(*ans, sep="\n")

### FIXED CODE ###

from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

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

n = int(input())
list = []
for i in range(n):
    list += [int(input())]

for i in range(n):
    a = list[i]
    del list[i]
    ans = max(list)
    list.insert(i,a)
    print(ans)

### FIXED CODE ###

n = int(input())
list = []
for i in range(n):
    list += [int(input())]

max_ = max(list)
for i in range(n):
    a = list[i]
    if a == max_:
        del list[i]
        ans = max(list)
        print(ans)
        list.insert(i,a)
        if ans == max_:
            for j in range(n-i-1):
                print(max_)
            break
    else:
        print(max_)
### BUGGY CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    surplus = (j * multiplier + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)]
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)]
        
        for j in range(13):        
            DP_table[(i + 1, j)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

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

from sys import stdin


def dp_solve(i, h, dp, K):
    for i in range(1, n):
        if i <= K:
            dp1 = min(dp)
            dp[i] = [min(dp1[0]+abs(h[i] - h[dp1[1]]), abs(h[i]-h[0])), i]
        else:
            for d in dp[i-K:i]:
                dp[i] = min(dp[i], [d[0]+abs(h[i] - h[d[1]]), i])
    return dp[n-1][0]


if __name__ == "__main__":
    n, K = map(int, input().split())
    h = list(map(int, stdin.readline().split()))
    inf = float('inf')
    dp = []
    for i in range(n):
        dp.append([inf, i])

    print(dp_solve(n-1, h, dp, K))


### FIXED CODE ###

from sys import stdin


def dp_solve(i, h, dp, K):
    for i in range(1, n):
        if i <= K:
            dp[i] = abs(h[i]-h[0])
        else:
            dp[i] = min([d + abs(h[i]-hk) for d, hk in zip(dp[i-K:i], h[i-K:i])])
    return dp[n-1]


if __name__ == "__main__":
    n, K = map(int, input().split())
    h = list(map(int, stdin.readline().split()))
    inf = float('inf')
    dp = [inf]*n

    print(dp_solve(n-1, h, dp, K))
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
li = [ i-1 for i in li ]

for num in range(n):
  print(li.index(num)+1, end = ' ' )
    

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
dct = { i:li[i] for i in range(n)}

for k, v in sorted(dct.items(), key=lambda x: x[1]):
    print(k+1, end = ' ' )
### BUGGY CODE ###

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

def solve():
    N, M = map(int, input().split())
    F = defaultdict(list)
    D = defaultdict(int)
    for _ in range(M):
        a, b = map(int, input().split())
        D[a] += 1
        D[b] += 1
        F[a] += F[a] + [b]
        F[b] += F[b] + [a]

    E = defaultdict(int)
    X = list()
    for a,d in D.items():
        if d%2==0:
            if d >= 6:
                E[6] += 1
            elif d == 4:
                E[4] += 1
                X.append(a)
            else:
                E[d] += 1
        else:
            E[1] += 1

    if E[1]==0 and (E[6]>=1 or E[4]>=3):
        res = 'Yes'
    elif E[4]==2:
        x, y = X
        q = set((y,))
        R = set((x,))
        while q:
            z = q.pop()
            R.add(z)
            q |= set(F[z])-R
        if set(F[x])&R == set(F[x]):
            res = 'No'
        else:
            res = 'Yes'
    else:
        res = 'No'
    return str(res)
if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

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

def solve():
    N, M = map(int, input().split())
    F = [list() for _ in range(N+1)]
    D = [int() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        D[a] += 1
        D[b] += 1
        F[a].append(b)
        F[b].append(a)

    E = [0 for _ in range(7)]
    X = list()
    for a,d in enumerate(D[1:], start=1):
        if d%2==0:
            if d >= 6:
                E[6] += 1
            elif d == 4:
                E[4] += 1
                X.append(a)
            else:
                E[d] += 1
        else:
            return 'No'
            E[1] += 1

    if E[6]>0 or E[4]>2:
        return 'Yes'

    elif E[4]<2:
        return 'No'

    else:
        x, y = X
        q = set((y,))
        R = set((x,))
        while q:
            z = q.pop()
            R.add(z)
            q |= set(F[z])-R
        if set(F[x])&R == set(F[x]):
            return 'No'
        else:
            return 'Yes'

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

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

cnt = 0
for i in range(N):
    c = 1
    for j in range(i+1):
        if P[i] <= P[j]:
            c *= 1
        else:
            c *= 0
    cnt += c
print(cnt)


### FIXED CODE ###

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

memo = [0] * N
memo[0] = 1
minn = P[0]
for i in range(1, N):
    if P[i] <= minn:
        memo[i] = 1
    else:
        memo[i] = 0
    minn = min(minn, P[i])
print(sum(memo))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    food=[]
    for _ in range(n):
        a,b=map(int, input().split())
        food.append([a,b])
    food.sort(key=lambda x:x[0]*-1)
    for j in range(n):
        a,b=food[j][0],food[j][1]
        for i in range(t-1,-1,-1):
            if i < a: 
                dp[i]=max(b,dp[i])
            else:
                dp[i]=max(dp[i-a]+b,dp[i])
    print(dp[t-1])
 
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    food=[]
    for _ in range(n):
        a,b=map(int, input().split())
        food.append([a,b])
    food.sort(key=lambda x:x[0]*-1)
    for j in range(n):
        a,b=food[j][0],food[j][1]
        dptmp=[0]*t
        for i in range(t):
            if i < a: 
                dptmp[i]=max(b,dp[i])
            else:
                dptmp[i]=max(dp[i-a]+b,dp[i])
        dp=dptmp
    print(dp[t-1])
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
l=[0]*N

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

ans=0    
for i in range(N):
    ans+=l[i:].count(0)
    l=list(map(lambda x:x-A[i],l))

print(ans)
    



### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections

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

l=[0]
for i in range(N):
    temp=l[-1]+A[i]
    l.append(temp)

c=collections.Counter(l)
#print(l)
#print(c)

_, count=zip(*c.most_common())

ans=0
for item in count:
    ans+=item*(item-1)//2
    
print(ans)
#for item in l:
### BUGGY CODE ###

N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ [int(it)-1 for it in input().split()] for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  else:
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue
      
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)


### FIXED CODE ###

N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ [int(it)-1 for it in input().split()] for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  else:
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue
    if (len(dw[_a]) < len(dw[_b])):
      _a,_b=_b,_a
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)
### BUGGY CODE ###

S = input()
T = input()
D = [[] for _ in range(26)]
for i, s in enumerate(S):
  D[ord(s) - 97].append(i + 1)
def bsearch(t, pos, loop):
  d = D[ord(t) - 97]
  l = len(d)
  if l < 1:
    return -1, 0
  if pos < d[0]:
    return d[0], loop
  if d[l - 1] <= pos:
    loop += 1
    return d[0], loop
  low = 0
  high = l
  while high - low > 1:
    mid = (high - low) // 2
    if pos < d[mid]:
      high = mid
    else:
      low = mid
  return d[high], loop
pos = 0
loop = 0
for t in T:
  pos, loop = bsearch(t, pos, loop)
  if pos == -1:
    print(-1)
    break
else:
  print(len(S) * loop + pos)

### FIXED CODE ###

import bisect
S = input()
T = input()
D = [[] for _ in range(26)]
for i in range(26):
  D[i] = [0] * S.count(chr(97 + i))
P = [0] * 26
for i, s in enumerate(S):
  n = ord(s) - 97
  D[n][P[n]] = i + 1
  P[n] += 1
pos = 0
loop = 0
for t in T:
  n = ord(t) - 97
  if D[n] == []:
    print(-1)
    break
  _d = bisect.bisect(D[n], pos)
  _pos = D[n][_d % len(D[n])]
  if _pos <= pos:
    loop += 1
  pos = _pos
else:
  print(len(S) * loop + pos)
### BUGGY CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()])
B = sorted([int(b) for b in input().split()])
C = sorted([int(c) for c in input().split()])
ans = 0

for i in range(N):
  for j in range(N):
    for k in range(N):
      if A[i] < B[j] < C[k]:
        ans += (N - k)
        break
print(ans)

### FIXED CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()])
B = [int(b) for b in input().split()]
C = sorted([int(c) for c in input().split()])
ans = 0

import bisect
for i in range(N):
  b = B[i]
  end_A = bisect.bisect_left(A, b)
  start_C = bisect.bisect_right(C, b)
  ans += end_A * (N - start_C)

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


trans = []
n = int(input())
for i in range(5):
	trans.append(int(input()))

town =[0 for _ in range(6)] 
town[0] = n

t = 0
while town[-1] != n:
	t += 1
	for i in reversed(range(5)):

		temp = min(town[i],trans[i])
		town[i] -= temp
		town[i+1] += temp
print(t)

### FIXED CODE ###


trans = []
n = int(input())
for i in range(5):
	trans.append(int(input()))

m=min(trans)
if n%m==0:
  print(n//m+4)
else:
  print(n//m+5)
### BUGGY CODE ###

import collections

n = int(input())
a_lst = [int(elem) for elem in input().split()]
c = collections.Counter(a_lst)
res1 = 0
for k in c.keys():
  if c[k] > 1:
    res1 += c[k] * (c[k] - 1) // 2

for i in range(n):
  res = res1
  lst = a_lst[:i]+a_lst[i+1:]
  res -= lst.count(a_lst[i])
  print(res)

### FIXED CODE ###

import collections

n = int(input())
a_lst = [int(elem) for elem in input().split()]
c = collections.Counter(a_lst)
res1 = 0
for k in c.keys():
  res1 += c[k] * (c[k] - 1) // 2

for i in range(n):
  res = res1
  res -= c[a_lst[i]] - 1
  print(res)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

dp = [0] * (1 << n)
dp[0] = 1

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        newbit = bit | (1 << j)
        if (a[i][j] == 1) and ((bit >> j) & 1 == 0):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

# 解説を参考に作成

def solve():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S))]

    if S[-1] == '?':
        dp[0] = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[0][int(S[-1])] = 1

    for i, s in enumerate(S[::-1][1:], 1):
        digit = pow(10, i, 13)
        if s == '?':
            for j in range(10):
                x = (j * digit) % 13
                for k in range(13):
                    # print(s, i, j, k, x)
                    dp[i][(x + k) % 13] += dp[i - 1][k] % (10 ** 9 + 7)
        else:
            x = (int(s) * digit) % 13
            for k in range(13):
                # print(s, i, 'X', k, x)
                dp[i][(x + k) % 13] += dp[i - 1][k] % (10 ** 9 + 7)
    print(dp[-1][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# #11254823を参考


def solve():
    S = input()
    mod = 10 ** 9 + 7

    '''
    桁数毎・余りの数字ごとのdpを作成するにあたり、mapを作る.
    たとえば新しい数字Yは前の数字Xの右側に新たに桁を作って
        Y = X(前の数字) * 10 + i(0 <= i <= 9)
    と表せる.
    この Y の余りは、
        Y % 13 = ((X % 13) * 10 + i) % 13
    と表せるので、10 * 13 のマップであらかじめ計算しておくことができる.
    このマップを以下で作っている.
        modmap[新しい桁の数字i][新しい余り(Y % 13 = k)] = 前の数字の時の余り(X % 13 = j)
    '''
    modmap = []
    for i in range(10):
        modmap.append([0] * 13)
        for j in range(13):
            k = (j * 10 + i) % 13
            modmap[i][k] = j

    # なぜ最初を1にするのか？
    # → Sの先頭に 0 を固定でつけても結果は変化しない. また付けた場合の最初の計算では余り0となる.
    # → どんなパターンでも共通の初期状態として使用できる.
    dp = [1] + [0] * 12
    for s in S:
        if s == '?':
            dp = [sum(dp[l] for l in modlist) % mod for modlist in zip(*modmap)]
        else:
            modlist = modmap[int(s)]
            dp = [dp[modlist[l]] % mod for l in range(13)]

    print(dp[5])


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

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

### FIXED CODE ###

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

if 0 in A:
  ans = 0
  
else:
  ans = 1
  for i in range(N):
    ans *= A[i]
    if ans > 10**18:
      ans = -1
      break

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

import fractions

n = int(input())
As = sorted(list(map(int, input().split(" "))))
maxa = As[0]
largest = 1

for i in range(n):
  gcd = 0
  prev = 0
  for idx, j in enumerate(As):
    if idx == i:
      continue
    gcd = j if gcd==0 else fractions.gcd(gcd, j)
    if gcd <= largest:
      break
  if gcd > largest:
    largest = gcd
print(largest)



### FIXED CODE ###

def gcd(a, b):
  l = max(a, b)
  s = min(a, b)
  if s == 0:
    return l
  else:
    return gcd(s, l%s)

n = int(input())
A = [0] + list(map(int, input().split())) + [0]
largest = 0
L = [0 for _ in range(n+2)]
R = [0 for _ in range(n+2)]
for i in range(1, n+2):
  L[i] = gcd(A[i], L[i-1])
  R[n-i+1] = gcd(R[n-i+2], A[n-i+1])

print(max(gcd(L[i-1],R[i+1]) for i in range(1, n+1)))
### BUGGY CODE ###

A=list(map(int,input().split()))
t=True
C=2019
if t:
    for i in range(A[1]):
        for t in range(A[1]+1):
            if t>i and i>=A[0]:
                if t-i>=2019:
                    C=0
                    t=False
                    break
                else:
                    if t*i%2019<C:
                        C=t*i%2019
print(C)

### FIXED CODE ###

l,r=list(map(int,input().split()))
f=True
C=2019
if (r-l)<2019:
    for i in range(l,r+1):
        if C==0:
            break
        for t in range(i+1,r+1):
            if t*i%2019<C:
                C=t*i%2019
                if C==0:
                    break
else:
    C=0
print(C)
### BUGGY CODE ###

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

import fractions

def gcdoflist(l):
    n=len(l)
    if n==1:
        return l[0]
    else:
        ans=l[0]
        for i in range(1,n):
            ans=fractions.gcd(ans,l[i])
        return ans
m_list=[]
#端点の場合
#右端
m_list.append(gcdoflist(al[0:n-1]))

#左端
m_list.append(gcdoflist(al[1:n]))
ans=max(m_list)
for i in range(1,n-1):
    left=al[0:i]
    right=al[i+1:n]
    temp=fractions.gcd(gcdoflist(left),gcdoflist(right))
    if temp>ans:
        ans=temp
print(ans)

### FIXED CODE ###

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

import fractions
ans=0
left=[0]
for i in range(1,n):
    ans=fractions.gcd(ans,al[i-1])
    left.append(ans)
#print(left)
right=[0 for i in range(n+1)]
for i in range(1,n+1):
    right[n-i]=fractions.gcd(right[n-i+1],al[n-i])
#print(right)

ans=0

for i in range(n):
    ans=max(ans,(fractions.gcd(left[i],right[i+1])))
print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
else:
    d=int(p**(1/n))
    k=1
    for i in range(d+1,0,-1):
        if p%(i**n)==0:
            k=i
            print(k)
            break
    else:
        print(k)

### FIXED CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
else:
    def r(n,p):
        d=int(p**(1/n))
        k=1
        for i in range(1,d+1):
            if p%(i**n)==0:
                k=i
        return k
    c=1
    while r(n,p)!=1:
        s=r(n,p)
        c*=s
        p=p/(s**n)
    print(c)
### BUGGY CODE ###

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

# TESTCASE #
test = ""
#test = \
"""
3 2
5 1 4
2 3
1 5
ans:
14
"""

"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
ans:
338
"""

"""
3 2
100 100 100
3 99
3 99
ans:
300
"""

"""
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
ans:
10000000001
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
### MAIN ###
        
n, m = map(int, input2().split())
a = list(map(int, input2().split()))
bcs = [tuple(map(int, input2().split())) for _ in range(m)]
bcs.sort()

for query in bcs:
    a.sort()
    for qi in range(query[0]):
        a[qi] = max(a[qi], query[1])
    
print(sum(a))
    

  


### FIXED CODE ###

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

import numpy as np

# TESTCASE #
test = ""
#test = \
"""
3 2
5 1 4
2 3
1 5
ans:
14
"""

"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
ans:
338
"""

"""
3 2
100 100 100
3 99
3 99
ans:
300
"""

"""
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
ans:
10000000001
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
### MAIN ###
        
n, m = map(int, input2().split())
a = np.array(list(map(int, input2().split())), dtype="int64")
bcs = [tuple(map(int, input2().split()))[::-1] for _ in range(m)]

a.sort()
bcs = sorted(bcs, reverse=True)

i = 0
for query in bcs:
    #print(query)
    a[i:i+query[1]] = np.maximum(a[i:i+query[1]], query[0])
    i += query[1]
    #print(a)    
print(np.sum(a))
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
V = []
for i in range(M):
    a, b = map(int, input().split())
    V.append((a-1, b-1))


def bfs(G):
    visited = [False] * N
    visited[0] = True
    que = deque([(0, -1, 0)])
    r = 0
    while que:
        ci, p, d = que.popleft()
        for ni in G[ci]:
            if visited[ni] is False:
                visited[ni] = True
                que.append((ni, ci, d+1))
                r = max(r, d+1)

    return r


ans = 0
for i in range(2 ** M):
    if bin(i).count('1') != N-1:
        continue
    else:
        G = {k: [] for k in range(N)}
        for j in range(M):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                (a, b) = V[j]
                G[a].append(b)
                G[b].append(a)
        if bfs(G) == N-1:
            ans += 1
print(ans)


### FIXED CODE ###

import itertools

N,M=map(int,input().split())
route=[list(map(int,input().split())) for _ in range(M)]
candidate=list(itertools.permutations(range(1,N+1)))

ans=0
for c in candidate:
  if c[0]==1:
    for i in range(N-1):
      l=sorted([c[i], c[i+1]])
      if l not in route:
         break
    else:
      ans+=1
print(ans)