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

N = int(input())
X = [int(i)  for i in list(input())]
xx = X.copy()
n = 0

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

def answer(n): # 10進数を入力
    ans = 0
    while(n != 0):
        n = n%popcnt(n)
        ans += 1
    return ans

for i in range(N):
    if X[i] == 0:
        xx[i] = 1
    else:
        xx[i] = 0
#     print(xx)
    # 2進数の変換
    for jj in range(1,len(xx)+1):
        n += xx[-jj]*2**(jj-1)
    print(answer(n))
    #初期化
    n = 0
    xx = X.copy()

### FIXED CODE ###

n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0

for b in x:
    # 整数にしていって，各popであまりをとる，一発目の値を各popで割った時のあまりがわかった
    if one_pop_count != 0:
        one_mod = (one_mod*2 + int(b) ) % one_pop_count
    zero_mod = (zero_mod*2 + int(b) ) % zero_pop_count

# f の前計算...popcountで割ったあまりをまたpopcountで割るの繰り返し
f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i] = pop_count[i//2] + i%2 # 最後の桁とそれ以外で分けるとpopcountできる
    f[i] = f[i % pop_count[i]] + 1

#pow2の前計算...2^iをpopcountで割ったあまりの計算
one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1, 220000): 
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

# n-1, n-2, ..., 0
for i  in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count # 負の数になっているから
            print(f[nxt]+1)
        else:
            print(0)
        
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)
### BUGGY CODE ###

# C

N=int(input())
A=list(map(int,input().split()))
p=10**9+7

Asum=[sum(A[i+1:])%p for i in range(len(A))]
print(sum((A[i]*Asum[i])%p for i in range(N))%p)

### FIXED CODE ###

# C

N=int(input())
A=list(map(int,input().split()))
p=10**9+7

sumA = sum(A)

sumA_2 = sum([a**2 for a in A])

print(((sumA**2-sumA_2)//2)%p)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for s in range(S+1):
        if s-A[i] >= 0:
            dp[i+1][s] = (dp[i][s] * 2 + dp[i][s-A[i]]) % MOD
        else:
            dp[i+1][s] = dp[i][s] * 2 % MOD
print(dp[N][S])



### FIXED CODE ###


def solve(N,S,A):
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    mod = 998244353
    for i, a in enumerate(A, 1):
        for s in range(S+1):
            if s-a >= 0:
                dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
            else:
                dp[i][s] = dp[i-1][s] * 2 % mod
    print(dp[N][S])

N, S = map(int, input().split())
A = list(map(int, input().split()))
solve(N,S,A)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    start_len = sum(A)
    temp_len = sum(A)
    sousa = 0
    if(start_len % 2 == 1):
        sousa += 1
    while(1):
        seikou1 = kazoe(N, A, start_len + sousa, sousa, "+", start_len)
        seikou2 = kazoe(N, A, start_len - sousa, sousa, "-", start_len)
        if(seikou1 == True or seikou2 == True):
            break
        sousa += 2
    print(sousa)
            
            
def kazoe(N,A,temp_len, sousa, mi_pl, start_len):
    if(temp_len == 0):
        return False
    mokuteki = temp_len/2
    temp = 0
    for i in range(N):
        temp += A[i]
        if(temp > mokuteki):
            break
    i1 = i-1
    kouho1 = temp - A[i]
    i2 = i
    kouho2 = temp
    if(mi_pl == "+"):
        if(kouho1 + sousa == mokuteki or start_len - kouho2 + sousa == mokuteki):
            return True
        else:
            return False
    else:
        if(start_len - kouho1 - sousa == mokuteki or kouho2 - sousa == mokuteki):
            return True
        else:
            return False

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    start_len = sum(A)
    mokuteki = start_len/2
    temp = 0
    for n in range(N):
        temp += A[n]
        if(temp >= mokuteki):
            break
    n1 = n-1
    kouho1 = temp - A[n]
    n2 = n
    kouho2 = temp
    kouho1_ = start_len - kouho1*2
    kouho2_ = kouho2*2 - start_len
    res = min(kouho1_, kouho2_)
    print(res)
            

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

n = int(input())
w = []
r = []
for i in range(n):
    s = str(input())
    s = sorted(s)
    if s in w:
        r[w.index(s)] += 1
    else:
        w.append(s)
        r.append(1)
ans = 0
for i in range(len(r)):
    ans += (r[i]*(r[i]-1))//2
print(ans)

### FIXED CODE ###

n = int(input())
s = [str(input()) for _ in range(n)]
e = []
for i in range(n):
    e.append("".join(sorted(s[i])))
e.sort()
g = [1]
for i in range(n-1):
    if e[i] != e[i+1]:
        g.append(1)
    else:
        g[-1] += 1
ans = 0
for i in g:
    ans += (i*(i-1)//2)
print(ans)
### BUGGY CODE ###

from itertools import product

R, G, B, N = map(int, input().split())
R_max = N // R
G_max = N // G
ans = 0
for r, g in product(range(R_max+1), range(G_max+1)):
    b, r = divmod((N - (r*R + g*G)), B)
    if r == 0 and b >= 0: ans += 1
print(ans)

### FIXED CODE ###

from itertools import product

R, G, B, N = map(int, input().split())
R_max = N // R
G_max = N // G
ans = 0
for r, g in product(range(R_max+1), range(G_max+1)):
    if N >= r*R + g*G and (N - (r*R + g*G)) % B == 0: ans += 1
print(ans)
### BUGGY CODE ###

[n,m] = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
x = sorted(x)

if n == 1:
    print(max(x) - min(x))
elif n >= m:
    print(0)
else:

    dif = []
    for i in range(m-1):
        dif.append(x[i+1] - x[i])

    for i in range(n - 1):
        dif.remove(max(dif))
    print(sum(dif))


### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
x = sorted(x)

if n == 1:
    print(max(x) - min(x))
elif n >= m:
    print(0)
else:
    dif = []
    for i in range(m - 1):
        dif.append(x[i+1] - x[i])
    dif = sorted(dif)
    dif = dif[:m-n]
    print(sum(dif))
### BUGGY CODE ###

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

res = [k] * n
for i in range(q):
  a = int(input())
  res = [(elem - 1) for elem in res]
  res[a - 1] += 1

for elem in res:
  if elem > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

import collections

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

a_lst = []
for i in range(q):
  a = int(input())
  a_lst.append(a)

res = [k - q] * n
c = collections.Counter(a_lst)
for k in c.keys():
  res[k - 1] += c[k]

for elem in res:
  if elem > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###


import sys

sys.setrecursionlimit(10000)


#約数リスト
def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    divisors.append(n)
    return divisors

def check(N,K):
    if N<K:
        return N==1
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return N % K == 1


def resolve():
    N = int(input())
    ys= make_divisors(N)
    ys2= set(make_divisors(N))
    lst=[]
    for i in range(2,N+1):
        ans = check(N,i)
        if ans:
            lst.append((i,N%i,(N-1)%i))
    print(len(lst))

if __name__ == "__main__":
    resolve()
    #unittest.main()

### FIXED CODE ###


def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    divisors.append(n)
    return divisors

def check(N,K):
    try:
        if N == K:
            return True
        if N % K ==1:
            return True
        if N<K:
            return False
        
        if N % K ==0:
            return check(N//K,K)
        else:
            return False
    except:
        return False

def resolve():
    N = int(input())
    ys= set(make_divisors(N))
    ys2= set([i for i in make_divisors(N-1) if check(N,i)])

    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


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

##################################################################
def main():
    Input = [input() for i in range(2)]
    N = int(Input[0])
    L = list(map(int,Input[1].split()))
    L.sort()
    ans = 0
    for i1 in range(0,N-2):
        a = L[i1]
        for i2 in range(i1+1,N-1):
            b = L[i2]
            i3 = i2+1
            while (i3<N and a+b>L[i3]):
                i3 += 1
            ans += i3 - i2 -1
    print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
##################################################################
def main():
    Input = [input() for i in range(2)]
    N = int(Input[0])
    L = list(map(int,Input[1].split()))
    L.sort()
    ans = 0
    for i1 in range(0,N-2):
        a = L[i1]
        for i2 in range(i1+1,N-1):
            b = L[i2]
            ans += bisect.bisect_left(L, a+b) - i2 - 1
    print(ans)



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

import sys
sys.setrecursionlimit(10**6)


N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 10**9 + 7


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow_mod(2, l, MOD)) % MOD * (pow_mod(2, N+r, MOD) + r * pow_mod(2, N+r-1, MOD))) % MOD
    ans %= MOD

print(ans)

### FIXED CODE ###

"""



"""

import sys
sys.setrecursionlimit(10**6)


N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 10**9 + 7


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow(2, l, MOD)) % MOD * (pow(2, N+r, MOD) + r * pow(2, N+r-1, MOD))) % MOD
    ans %= MOD

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

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = sorted(nl())

for i in range(m):
    b, c = nm()
    a += [c] * b

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


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = sorted(nl())

pos = 0

changer = []

for i in range(m):
    b, c = nm()
    changer.append((c, b))

changer = sorted(changer)[::-1]


for i in range(m):

    c = changer[i]
    for j in range(c[1]):
        while pos < n:
            if a[pos] < c[0]:
                a[pos] = c[0]
                break
            pos += 1
    if pos >= n:
        break

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

# coding: utf-8
def main():
    N, M = map(int, input().split())
    a = []
    for i in range(M):
        a.append(int(input()))
    
    #print("a", a)
    
    dp = ([0] * N)
    dp.append(1)
    dp.append(0)
    mod = 1000000007
    
    for s in reversed(range(N)):
        if s in a: # xだったら
            if s+1 in a:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()

### FIXED CODE ###

# coding: utf-8
def main():
    N, M = map(int, input().split())

    a = [True] * (N+1)
    #s = [True for _ in range(N+1)]
    for _ in range(M):
        a[int(input())] = False
    #print(a)
    
    #a = []
    #for i in range(M):
    #    a.append(int(input()))
    
    dp = [0] * (N)
    dp.append(1)
    dp.append(0)
    mod = 10**9 + 7
    
    for s in reversed(range(N)):
        if a[s] == False: # xだったら
            if a[s+1] == False:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100010)

N, M = map(int,input().split())
E = [[] for k in range(N)]

for k in range(M):
    X, Y, Z = map(int,input().split())
    E[X-1].append(Y-1)
    E[Y-1].append(X-1)
G = [-1]*N

def dfs(now,group):
    if G[now] == -1:
        G[now] = group
        for tsugi in E[now]:
            dfs(tsugi,group)

ans = 0
for k in range(N):
    if G[k] == -1:
        dfs(k,ans)
        ans += 1
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100010)

N, M = map(int,input().split())
E = [[] for k in range(N)]

for k in range(M):
    X, Y, Z = map(int,input().split())
    E[X-1].append(Y-1)
    E[Y-1].append(X-1)
G = [-1]*N

def dfs(now,group):
    if G[now] == -1:
        G[now] = group
        for tsugi in E[now]:
            dfs(tsugi,group)

ans = 0
for k in range(N):
    if G[k] == -1:
        dfs(k,ans)
        ans += 1
print(ans)
### BUGGY CODE ###


import math
H = int(input())


def iterated_power(z: int, n: int, mod=None) -> int:
    beta = bin(n)[2:]

    Z, q, t = z, 0, len(beta)
    while beta[t - q - 1] == '0':
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        q += 1
    result = Z

    for k in range(q + 1, t):
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        if beta[t - k - 1] == '1':
            result = result * Z
            if mod is not None:
                result = result % mod

    if mod is not None:
        result = result % mod

    return result

cnt = 0
while True:
    H = math.floor(H/2)
    cnt += 1
    if H ==1:
        break
cnt += 1

ans = iterated_power(2, cnt) - 1

print(ans)


### FIXED CODE ###


H = int(input())


def iterated_power(z: int, n: int, mod=None) -> int:
    """ 繰り返し二乗法でn**kを求める（再帰処理は使わない）
    >>> p = Prime()
    >>> p.iterated_power(3, 10)
    59049
    >>> p.iterated_power(3, 10, 10)
    9
    """
    beta = bin(n)[2:]

    Z, q, t = z, 0, len(beta)
    while beta[t - q - 1] == '0':
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        q += 1
    result = Z

    for k in range(q + 1, t):
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        if beta[t - k - 1] == '1':
            result = result * Z
            if mod is not None:
                result = result % mod

    if mod is not None:
        result = result % mod

    return result


ans = iterated_power(2, H.bit_length()) - 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
ans, s, i = 0, set(), 0

while i < N:
    j = 1
    while i+j <= N-1 and A[i] == A[i+j]:
        j += 1
    if j > 1:
        ans += j 
        s.add(i)
        i += j
    else:
        border, sadd = A[i] // 2, True
        for j in s:
            if A[i] % A[j] == 0:
                ans += 1
                sadd = False
                break
            elif A[j] > border:
                break
        if sadd:
            s.add(i)
        i += 1

print(N - ans)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
if N == 1:
    print(1)
elif A[0] == 1 and A[1] == 1:
    print(0)
elif A[0] == 1:
    print(1)
else:
    Eratos = [False]*1000001
    ans = 0
    for i in range(N):
        if Eratos[A[i]]:
            ans += 1
        else:
            if i < N-1 and A[i] == A[i+1]:
                ans += 1
            for j in range(A[i], 1000001, A[i]):
                Eratos[j] = True
    print(N-ans)
### BUGGY CODE ###

A,B,K=map(int,input().split())
L=range(A,A+K)
R=range(B-K+1,B+1)
S=[i for i in range(A,B+1) if i in L or i in R]
for i in range(len(S)):
  print(S[i])

### FIXED CODE ###

A,B,K=map(int,input().split())
S=[i for i in range(A,B+1) if i<A+K or i>=B-K+1]
for i in range(len(S)):
  print(S[i])
### BUGGY CODE ###

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

count = 0
for x in range(0,K+1):
  for y in range(0,K+1):
    for z in range(0,K+1):
      if S == x + y + z:
        count = count + 1
          
print(count)

### FIXED CODE ###

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

count = 0
for x in reversed(range(0,K+1)):
  for y in reversed(range(0,K+1)):
    z = S - x - y
    if z >= 0 and z <= K:
      count = count + 1
          
print(count)
### BUGGY CODE ###

import numpy as np
N = int(input())
A_lis = list()
for i in range(N):
    A_lis.append(int(input()))

A_lis = np.array(A_lis)
for i in range(N):
    ind = np.ones(N, dtype=bool)
    ind[i] = False
    print(max(A_lis[ind]))

### FIXED CODE ###

import numpy as np
N = int(input())
A_lis = [int(input()) for _ in range(N)]

num = sorted(A_lis, reverse=True)[:2]
for i in A_lis:
    if i != num[0]:
        print(num[0])
    else:
        print(num[1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))
### BUGGY CODE ###

a,b,n=map(int,input().split())
res=0
x=n
for x in range(min(b,n+1)):
    res=max(res,int(a*x/b)-a*int(x/b))
print(res)


### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(b-1,n)
max_res=int(a*x/b)-a*int(x/b)
print(max_res)
### BUGGY CODE ###

N = int(input())

srt_n = str(N)
keta = len(srt_n)

#ans = [0] * ( keta + 1 )
N_list = [0] * (keta+1)
ans_num = 0

for i in reversed(range(keta)):
    N_list[keta-i-1] = int(srt_n[i])

for i in range(keta+1):
    if N_list[i] == 5 and N_list[i+1] >= 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    elif N_list[i] > 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    else:
        #ans[i] =  N_list[i]
        ans_num += N_list[i]
#print(ans)
print(ans_num)

### FIXED CODE ###

N = input()

keta = len(N)

#ans = [0] * ( keta + 1 )
N_list = [0] * (keta+1)
ans_num = 0

for i in reversed(range(keta)):
    N_list[keta-i-1] = int(N[i])

for i in range(keta+1):
    if N_list[i] == 5 and N_list[i+1] >= 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    elif N_list[i] > 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    else:
        #ans[i] =  N_list[i]
        ans_num += N_list[i]
#print(ans)
print(ans_num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))

table = [0] * (max(a) + 1)
for x in a: table[x] += 1
#print(table)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors

res = 0
for x in a:
  if table[x] > 1: continue
  for y in make_divisors(x):
    if x == y: continue
    if table[y]: break
  else: res += 1
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mx = max(a)
table = [0] * (mx + 1)
for x in a: table[x] += 1
#print(table)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors

res = set(a)
#print(res)
for i in range(1, mx + 1):
  if table[i] == 0: continue
  for j in range(i, mx + 1, i):
    if i == j:
      if table[j] > 1:
        res.discard(j)
      continue
    if table[j]: res.discard(j)
print(len(res))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)

bc=[]
for i in range(m):
    B = list(map(int, input().split()))
    bc.append(B)
bc.sort(key=lambda x: x[1])
#print(bc)

for i in range(m):
    x = bisect.bisect_left(a, bc[i][1])
    if x!=0:
        a += [bc[i][1]]*min(bc[i][0],x)
    #print(a)
a.sort()
print(sum(a[len(a)-n:]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)
#print(bc)
cnt=0
for i in range(n):
    if bc[cnt][0]>0:
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    else:
        cnt+=1
        if cnt==len(bc):
            break
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    #print(cnt,bc,a)
print(sum(a))
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
s=input()
ss=s.replace("x","")
if ss!=ss[::-1]:
 print(-1)
else:
 e=[]
 for i in range(len(ss)):
  e.append(ss[i])
 j=0
 k=0
 d1=[]
 jj=0
 kk=0
 d2=[]
 for i in range(len(s)):
  if k<len(e) and s[i]==e[k] :
    d1.append(s[j:i])
    j=i+1
    k+=1
  if kk<len(e) and s[::-1][i]==e[kk] :
    d2.append(s[::-1][jj:i])
    jj=i+1
    kk+=1
 d1.append(s[j:])
 d2.append(s[::-1][jj:]) 
 dd=0  
 for i in range(len(d1)):
   dd+=abs(len(d1[i])-len(d2[i]))
 print(dd//2)


### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
s=input()
ss=s.replace("x","")
if ss!=ss[::-1]:
 print(-1)
else:
 e=[]
 for i in range(len(ss)):
  e.append(ss[i])
 j=0
 k=0
 d1=[]
 jj=0
 kk=0
 d2=[]
 sr=s[::-1]
 for i in range(len(s)):
  if k<len(e) and s[i]==e[k] :
    d1.append(s[j:i])
    j=i+1
    k+=1
  if kk<len(e) and sr[i]==e[kk] :
    d2.append(sr[jj:i])
    jj=i+1
    kk+=1
 d1.append(s[j:])
 d2.append(sr[jj:]) 
 dd=0  
 for i in range(len(d1)//2):
   dd+=abs(len(d1[i])-len(d2[i]))
 print(dd)