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

n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
memo = {}
import sys
sys.setrecursionlimit(100000)
def dfs(rest, group):
    if (rest, group) in memo:
        return memo[rest, group]
    if rest == 0:
        return 1
    if group == a-1:
        return 0
    res = dfs(rest, group-1)
    for k in xrange(c, min(rest/group, d)+1):
        r = dfs(rest-k*group, group-1)
        r = (r * fact[rest]) % MOD
        r = (r * pow(pow(fact[group], MOD-2, MOD), k, MOD)) % MOD
        r = (r * pow(fact[rest-k*group], MOD-2, MOD)) % MOD
        r = (r * pow(fact[k], MOD-2, MOD)) % MOD
        res = (res + r) % MOD
    memo[rest, group] = res
    return res
for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
print dfs(n, b)


### FIXED CODE ###

n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    for i in rn:
        x = frev[n-i]
        dp[i] = (dp[i] + sum(dp[i-g*j] * fact[n-i+g*j] * x * pow(y, j, MOD) * frev[j] for j in xrange(c, min(d, i/g)+1))) % MOD
print dp[n]
### BUGGY CODE ###

N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
#被り探し
for i in range(N):
  d = e[i]
  e[i] = e[i]+ 9999999
  try:
    f = e.index(d)
    break
  except:
    pass
for j in range(N+1):
  print(comb(N+1,j+1,mod)-comb(i+N-f,j,mod))

### FIXED CODE ###

N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
kai = [0]*(N+3)
from collections import Counter
c = Counter(e).most_common(1)[0][0]
g = e.index(c)
e.remove(c)
f = e.index(c) +1
e = []
for i in range(N+3):
  if i ==0:
    kai[i] = 1
  else:
    kai[i] = (kai[i-1]*(i))%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=kai[n] 
  b=kai[k] 
  c=kai[n-k] 
  b = pow(b,mod-2,mod)
  c = pow(c,mod-2,mod)
  return (a*b*c)%mod
h = [1]*((N+6)//2)
for j in range((N+4)//2):
  h[j+1] = comb(N+1,j+1,mod)
for j in range(N+1):
  if N-j>N/2:
    print((h[j+1]-comb(g+N-f,j,mod)+mod)%mod)
  else:
    print((h[N-j]-comb(g+N-f,j,mod)+mod)%mod)
### BUGGY CODE ###

n, k = [int(elem) for elem in input().split()]
h = [int(elem) for elem in input().split()]

dp=[10**10]*n
dp[0] = 0
for i in range(0, n):
  for j in range(1, k+1):
    if len(h) > (i+j):
      tmp = dp[i] + abs(h[i] - h[i+j])
      if dp[i+j] > tmp:
          dp[i+j] = tmp
print(dp[-1])

### FIXED CODE ###

INF = 10**10
 
def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
 
    dp = [INF]*n
    dp[0] = 0
 
    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import numpy as np

def F2_GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[[pivot,rank]] = A[[rank,pivot]]
        for row in range(rank+1,len(A)):
            if (row != rank and A[row][col]):
                A[row] ^= A[rank]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

use_digit = []
ans = 0
for j in range(60)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        use_digit.append(j)

a = np.zeros((N,len(use_digit)), dtype=bool)
k = 0
for k,j in enumerate(use_digit):
    for i in range(N):
        if A[i]>>j & 1:
            a[i][k] = 1
        else:
            a[i][k] = 0

g = F2_GaussJordan(a,False)

s = 0
for i in range(N):
    s = max(s,s^sum([g[i][j]*2**use_digit[j] for j in range(len(use_digit))]))
ans += 2*s

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

for i in range(N):
    A[i] &= ~xor

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)
### BUGGY CODE ###

n = int(input())

A = []
B = []
for i in range(n):
    s  = "".join(list(sorted(list(input())))) 
    if s not in A:
        A.append(s)
        B.append(1)
    else:
        B[A.index(s)] += 1
c = 0
for i in B:
    if i >= 2:
        c += int(i * (i - 1)/2)
print(c)

### FIXED CODE ###

n = int(input())
import itertools
A = []
t = 0
for i in range(n):
    A.append("".join(sorted(list(input()))))


import collections

C = collections.Counter(A)


for i in C.values():
    t += i * (i - 1) // 2
print(t)
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7 

tot = 2 ** n - 1
ans = tot - cmb(n, a) - cmb(n, b)
print(ans % MOD)

### FIXED CODE ###

mod = 10 ** 9 + 7 
def cmb(n, r, mod):
    r = min(r, n -r)
    if r == 0: return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod

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


ans = pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)
print(ans % mod)
### BUGGY CODE ###

import  numpy as np
n,k,q = map(int,input().split())
a = []
while True:
  try:
    a.append(int(input()))
  except:
    break

score = np.ones(n)*k

for i in range(q):
  score -=1
  score[a[i]-1] += 1

for i in score:
  if i>=1:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

n,k,q = map(int,input().split())
a = []
while True:
  try:
    a.append(int(input()))
  except:
    break

score = [k-q]*n

for i in range(q):
  score[a[i]-1] +=1

for i in score:
  if i>=1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    a_list = input().split()
    if a_list[0] == "1":
        S = S[::-1]
    elif a_list[1] == "1":
        S = a_list[2] + S
    else:
        S = S + a_list[2]
print(S)

### FIXED CODE ###

from collections import deque
S = input()
ans = deque(S)
Q = int(input())
rev = False
for i in range(Q):
    a_list = input().split()
    if a_list[0] == "1":
        if rev == True:
            rev = False
        else:
            rev = True
    elif (a_list[1] == "1" and rev == False) or (a_list[1] == "2" and rev == True):
        ans.appendleft(a_list[2])
    else:
        ans.append(a_list[2])
if rev:
    ans.reverse()
ans = "".join(ans)
print(ans)
### BUGGY CODE ###

from math import ceil, log
from operator import __or__

N = int(input())
S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

ABC = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * ((1 << (1 + ceil(log(length, 2)))) - 1)
        self.origin = len(self.data) >> 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[(i << 1) + 1], self.data[(i << 1) + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, (k << 1) + 1, l, (l + r) >> 1),
                self._query(start, stop, (k << 1) + 2, (l + r) >> 1, r),
            )


S2 = [ABC[s] for s in S]

segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    segs[S2[i]].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        i = int(q2) - 1
        segs[S2[i]].update(i, False)
        letter = ABC[q3]
        segs[letter].update(i, True)
        S2[i] = letter
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)



### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    Q = int(input())
    t = [input().split() for _ in range(Q)]

    d = [0] * n + [1 << ord(c) - 97 for c in s]
    for i in range(n - 1, 0, -1):
        d[i] = d[i + i] | d[i - ~i]
    for q, a, b in t:
        i, s = int(a) + n - 1, 0
        if q < "2":
            d[i] = 1 << ord(b) - 97
            while i > 1:
                i //= 2
                d[i] = d[i + i] | d[i - ~i]
        else:
            j = int(b) + n
            while i < j:
                if i & 1:
                    s |= d[i]
                    i += 1
                if j & 1:
                    j -= 1
                    s |= d[j]
                i //= 2
                j //= 2
            print(bin(s).count("1"))


main()
### BUGGY CODE ###

n = input()
l = len(n)

if l < 4:
    print(0)
    exit()

mody = 2019
cnt = 0
for i in range(l-3):
    x = int(n[i:i+4])
    x %= mody
    if x == 0:
        cnt += 1
    for j in range(i + 4, l):
        x = 10 * x + int(n[j])
        x %= mody
        if x == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter
S = list(map(int, input()))
P = 2019

def solve(S,P):
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]
print(solve(S,P))
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def dfs(u, cost):
        visited[u] = True
        for v, w in edge[u]:
            if costs.get(v) and costs[v] != cost + w:
                print("No")
                sys.exit()
            costs[v] = cost + w
            dfs(v, cost + w)

    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = defaultdict(list)

    for _ in range(m):
        l, r, d = map(int, readline().split())
        edge[l].append((r, d))

    visited = [False] * (n + 1)

    for u in range(1, n + 1):
        costs = dict()
        if not visited[u]:
            dfs(u, 0)
    print("Yes")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)

    for _ in range(m):
        l, r, d = map(int, readline().split())
        edge[l].append((r, d))
        edge[r].append((l, -d))

    visited = [False] * (n + 1)

    for x in range(1, n + 1):
        costs = dict()
        if not visited[x]:
            costs[x] = 0
            que = deque()
            que.append((x, 0))
            while que:
                u, cost = que.popleft()
                visited[u] = True
                while edge[u]:
                    v, w = edge[u].pop()
                    if v in costs:
                        if costs[v] != cost + w:
                            print("No")
                            sys.exit()
                    costs[v] = cost + w
                    que.append((v, cost + w))

    print("Yes")


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

N = int(input())

A = []

for i in range(N):
    A.append(int(input()))

for i in range(N):
    if i == 0:
        print(max(A[1:]))
    elif i == N-1:
        print(max(A[:N-1]))
    else:
        print(max(max(A[:i]), max(A[i+1:])))



### FIXED CODE ###

N = int(input())
maxv1 = 0
maxv2 = 0

for i in range(N):
    a = int(input())
    if a >= maxv1:
        maxv1, maxv2 = a, maxv1
        flag = i
        continue
    if a >= maxv2:
        maxv2 = a

for i in range(N):
    if i == flag:
        print(maxv2)
    else:
        print(maxv1)
### BUGGY CODE ###

def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    temp=str(n)+' '+str(w)
    if(temp in bag):
        return bag[temp]
    if(weight[n-1]<=w):
        bag[temp]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[temp]
    else:
        bag[temp]=knapsack(n-1,w)
        return bag[temp]
n,w=map(int,input().split())
weight=[]
value=[]
bag=dict()
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

### FIXED CODE ###

import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
A = [int(input()) for _ in range(N)]
INF = float('inf')

cnt = 0
X = A
while len(X) > 0:
    cnt += 1
    Y = []
    dp = [INF] * (len(X) + 1)
    for a in X:
        idx = bisect_left(dp, a)
        if dp[idx] == INF:
            dp[idx] = a
        else:
            Y.append(a)
    X = Y


print(cnt)


### FIXED CODE ###

from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
INF = float('inf')

dp = [-A[0]]
cnt = 1
for i in range(1, N):
    a = -A[i]
    idx = bisect_right(dp, a)
    if idx == cnt:
        dp.append(a)
        cnt += 1
    else:
        dp[idx] = a

print(cnt)
### BUGGY CODE ###

from collections import *
s = input()
p = 2019
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
    v += int(i)*k
    r += c[v%p]
    c[v%p] += 1
    k *= 10
print(r)

### FIXED CODE ###

import numpy as np
s = input()
y = 2019
dp = np.zeros(y, dtype="int64")
tmp = np.zeros(y, dtype="int64")
k = 1
r = 0
for c in s[::-1]:
    i = int(c)*k%y
    tmp[i:] = dp[:y-i]
    tmp[:i] = dp[y-i:]
    tmp[i] += 1
    dp, tmp = tmp, dp
    r += dp[0]
    k *= 10
    k %= y
print(r)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(input().split())
    ans = ','.join(A)

    Q = int(input())

    replaces = []
    for i in range(Q):
        pp, ss = input().split()
        replaces.append([pp, ss])

    for varcher in replaces:
        ans = ans.replace(varcher[0], varcher[1])
        print(sum(map(int, ans.split(','))))


resolve()

### FIXED CODE ###

from collections import Counter


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    C = Counter(A)
    ANS = 0
    for i in C:
        ANS += i * C[i]

    for _ in range(Q):
        B, X = map(int, input().split())
        ANS += X * C[B]
        C[X] += C[B]

        ANS -= B * C[B]
        del(C[B])
        print(ANS)

resolve()
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    for i, e in enumerate(reversed(S)):
        rmd = (int(e)*10**i + rmd) % 2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    num_rate = 1
    L = len(S)
    for i in range(L):
        rmd = (int(S[L-i-1])*num_rate + rmd) % 2019
        num_rate = num_rate*10%2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

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

x = int(input())
n, y = 100, 0
while n < x:
    n = n % 1.01
    y = y + 1
print(y)

### FIXED CODE ###

x = int(input())
deposit, year = 100, 0
while deposit < x:
    deposit = deposit * 101 // 100
    year += 1
print(year)
### BUGGY CODE ###

def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((S+1), dtype=int)
    dp[0] = 2
    if An[0] <= S:
        dp[An[0]] = 1

    for n in range(1, N):
        for k in range(S, -1, -1):
            if k + An[n] <= S:
                dp[k+An[n]] = (dp[k+An[n]] + dp[k]) % 998244353
            dp[k] = (dp[k] * 2) % 998244353

    print(dp[S])
                
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((S+1), dtype=int)
    dp[0] = 2
    if An[0] <= S:
        dp[An[0]] = 1

    for n in range(1, N):
        dp *= 2
        dp[An[n]:] += dp[:-An[n]] // 2
        dp %= 998244353

    print(dp[S])
                
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    while num%2==0:
        d.add(2)
        num //= 2
    for i in range(3,int(sqrt(num))+1,2):
        while num%i==0:
            d.add(i)
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    st = set()
    for i in x:
        for j in pfact(i):
            if j not in st:
                st.add(j)
            else:
                ans = 'setwise coprime'
                break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
c = [str(a.count(i)) for i in range(1, n+1)]
print('\n'.join(c))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
l = [str(0) for i in range(n)]
key = list(c.keys())
for i in range(len(list(c.keys()))):
    l[key[i]-1] = str(c[key[i]])
print('\n'.join(l))
### BUGGY CODE ###

N, M = map(int, input().split())
a_list = list(map(int, input().split()))
items = []
for i in range(M):
    items.append(tuple(map(int, input().split())))

ans = 0
a_list.sort()

import heapq

heapq.heapify(a_list)

for i in range(M):
    b, c = items[i]

    while b >= 1:
        q = heapq.heappop(a_list)
        if c > q:
            heapq.heappush(a_list, c)
        else:
            heapq.heappush(a_list, q)
            break
        b -= 1
print(sum(a_list))


### FIXED CODE ###

import sys

N, M = map(int, sys.stdin.readline().split())
a_list = list(map(int, sys.stdin.readline().split()))
items = []
for i in range(M):
    items.append(tuple(map(int, sys.stdin.readline().split())))


from collections import defaultdict

tar = defaultdict(int)
for a in a_list:
    tar[a] += 1

for i in range(M):
    b, c = items[i]
    tar[c] += b

tar = sorted(tar.items(), key=lambda x: -x[0])

cnt = 0
ans = 0
for k, v in tar:
    if cnt + v <= N:
        cnt +=v
        ans += k*v
    else:
        ans += k*(N-cnt)
        cnt = N
    if cnt >= N:
        break
print(ans)