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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

IN = 'sample-1.in'  # sample case for local test
def local_test():
    try:
        from pcm.utils import set_stdin
        import sys
        import os
        if len(sys.argv) == 1:
            set_stdin(os.path.dirname(__file__) + '/test/' + IN)
    except:
        pass


def preprocess():
    import sys
    import os
    import time
    import re
    from pydoc import help
    import string
    import math
    import numpy as np
    from operator import itemgetter
    from collections import Counter
    from collections import deque
    from collections import defaultdict as dd
    import fractions
    from heapq import heappop, heappush, heapify
    import array
    from bisect import bisect_left, bisect_right, insort_left, insort_right
    from copy import deepcopy as dcopy
    import itertools
    sys.setrecursionlimit(10**7)
    INF = 10**20
    GOSA = 1.0 / 10**10
    MOD = 10**9+7
    def LI(): return [int(x) for x in sys.stdin.readline().split()]
    def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
    def LF(): return [float(x) for x in sys.stdin.readline().split()]
    def LS(): return sys.stdin.readline().split()
    def I(): return int(sys.stdin.readline())
    def F(): return float(sys.stdin.readline())
    def DP(N, M, first): return [[first] * M for n in range(N)]
    def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]


def solve():
    global S, N
    preprocess()
    N = int(input())

    S = []
    for n in range(N):
        S.append(list(input()))

    res = 0
    for n in range(N):
        if check(n):
            res += N

    print(res)

def check(move):
    for i in range(N):
        for j in range(i+1, N):
            if S[(i-move)%N][j] != S[(j-move)%N][i]:
                return False
    return True


if __name__ == "__main__":
    local_test()
    solve()

### FIXED CODE ###

def solve():
    global S, N
    N = int(input())

    S = []
    for n in range(N):
        S.append(list(input()))


    res = 0
    for n in range(N):
        if check(n):
            res += N

    print(res)

def check(move):
    for i in range(N):
        for j in range(i+1, N):
            if S[(i-move)%N][j] != S[(j-move)%N][i]:
                return False
    return True


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

from math import factorial

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

X_max = 0
X_min = 0

for i in range(N-K+1):
    n = factorial(N-1-i) // factorial(K-1) // factorial(N-K-i)
    X_max += n*A[-(i+1)]
    X_min += n*A[i]

print((X_max - X_min) % 1000000007)

### FIXED CODE ###

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

p = 1000000007
X_max = 0
X_min = 0


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


for i in range(N-K+1):
    n = cmb(N-1-i, K-1, p)
    X_max += n*A[-(i+1)]
    X_max %= p
    X_min += n*A[i]
    X_min %= p

print(int((X_max - X_min) % p))
### BUGGY CODE ###

import itertools
N,M=map(int,input().split())
A,B=[0]*M,[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())

res=0
for m in range(M):
    m+=1
    for p in itertools.permutations(range(M),m):
        path=[]
        if A[p[0]]==1:
            path.append(A[p[0]])
        else:
            continue
        path.append(B[p[0]])
        for i in range(len(p)-1):
            if A[p[i+1]]==path[-1]:
                path.append(B[p[i+1]])
            elif B[p[i+1]]==path[-1]:
                path.append(A[p[i+1]])
            else:
                break
        else:
            path.sort()
            if path==list(range(1,N+1)):
                res+=1
print(res)

### FIXED CODE ###

import itertools
N,M=map(int,input().split())
edges=[]
for i in range(M):
    edges.append(list(map(int,input().split())))

res=0
for i in itertools.permutations(range(2,N+1),N-1):
    path=[1]+list(i)
    check=[sorted(path[i:i+2]) in edges for i in range(len(path)-1)]
    if not False in check:
        res+=1
print(res)
### BUGGY CODE ###

Md,MN=1000000007,1000006
fac,ifac,a,res=[1],[1],[0],0
for i in range(1,MN):
    fac.append(fac[-1]*i%Md)
    ifac.append(pow(fac[-1],Md-2,Md))
def C(x,y):
    if(x<y):
        return 0
    return fac[x]*ifac[y]*ifac[x-y]
def D(x,y):
    return C(x-y+1,y)

n=int(input())
for i in range(1,n):
    if i*2-n>=0:
        a.append(D(n-3,n-i-1)*fac[i]*fac[n-i-1]%Md)
    else:
        a.append(0)
for i in range(n-1,0,-1):
    a[i]=(a[i]-a[i-1])%Md
    res=res+a[i]*i
res=res%Md
print(res)


### FIXED CODE ###

Md,MN=1000000007,1000006
fac,ifac,a,res,inv=[1,1],[1,1],[0],0,[1,1]
for i in range(2,MN):
    inv.append(inv[Md%i]*(Md-Md//i)%Md)
    fac.append(fac[-1]*i%Md)
    ifac.append(ifac[-1]*inv[i]%Md)
def C(x,y):
    if(x<y):
        return 0
    return fac[x]*ifac[y]*ifac[x-y]
def D(x,y):
    return C(x-y+1,y)

n=int(input())
for i in range(1,n):
    if i*2-n>=0:
        a.append(D(n-3,n-i-1)*fac[i]*fac[n-i-1]%Md)
    else:
        a.append(0)
for i in range(n-1,0,-1):
    a[i]=(a[i]-a[i-1])%Md
    res=res+a[i]*i
res=res%Md
print(res)
### BUGGY CODE ###

n = int(input())
N = [i for i in range(n)]
A = list(map(int,input().split()))
L = [N[i]+A[i] for i in range(n)]
R = [N[j]-A[j] for j in range(n)]
ans = 0
for i in range(n):
  for j in range(i+1,n):
    if L[i] == R[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 ###

S = input()
N = len(S)

rec = [[1 for i in range(N)]]
while True:
    li = [0 for i in range(N)]
    n = len(rec)
    for i in range(N):
        if S[i] == 'R':
            li[i+1] += rec[n-1][i]
        else:
            li[i-1] += rec[n-1][i]
    if n >= 2:
        if li == rec[n-2]:
            break
    rec.append(li)
n = len(rec)
if n%2 == 0:
    print(*rec[n-2])
else:
    print(*rec[n-1])


### FIXED CODE ###

S = input()
N = len(S)

li = [0]
char = 'R'
for i in S:
    n = len(li)
    if i == char:
        li[n-1] += 1
    else:
        li.append(1)
        char = i
n = len(li)
ans = []
for i in range(n//2):
    k = li[2*i] + li[2*i+1]
    for j in range(li[2*i] - 1):
        ans.append(0)
    if (k%2 == 0):
        ans.append(int(k/2))
        ans.append(int(k/2))
    else:
        if li[2*i]%2 == 0:
            ans.append(int(k//2))
            ans.append(int(k//2) + 1)
        else:
            ans.append(int(k//2) + 1)
            ans.append(int(k//2))
    for j in range(li[2*i+1] - 1):
        ans.append(0)

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

S=input()
N=len(S)+1
LEFT=[0]
RIGHT=[0]
left=0
right=0
for i in range(N-1):
  if S[i]==">":
    left=0
  else:
    left+=1
  LEFT+=[left]
for i in range(N-2,-1,-1):
  if S[i]=="<":
    right=0
  else:
    right+=1
  RIGHT.insert(0,right)
ans=0  
for i in range(N):  
  ans+=max(LEFT[i],RIGHT[i])
print(ans)  

### FIXED CODE ###

import itertools
S=input()
N=len(S)+1
ans=0
KEY=[]
gr=itertools.groupby(list(S))
i=0
for key,group in gr:
  n=len(list(group))
  ans+=n*(n+1)//2
  KEY+=[n]
  if key==">" and i!=0:
    ans-=min(KEY[i-1],KEY[i])
  i+=1
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    newA=list(A)
    if i in newA:
        while i in newA:
            newA.remove(i)
        print(len(A)-len(newA))
    else:
        print(len(A)-len(newA))



### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import collections
new_A=collections.Counter(A)
for i in B:
    print(new_A[i])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    alr[x] = False
    alr[y] = False
count = 0
for i in range(N):
    if alr[i] and p[i] == i:
        count += 1
i = 0
while True:
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
    if False in alr:
        i = alr.index(False)
    else:
        break
print(count)
                
    
        

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    xy[y].append(x)
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for k in xy[j]:
                if not alr[k]:
                    alr[k] = True
                    stack.append(k)
                    numlist.add(k)
        indlist = set([p[i] for i in numlist])
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
x = []
y = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
ans = 0

while(1):
    if m == 0:
        break
    mintmp = min(x)
    tmp = x.index(mintmp)
    if y[tmp] <= m:
        ans += mintmp*y[tmp]
        m -= y[tmp]
        x.pop(tmp)
        y.pop(tmp)
    else:
        ans += mintmp*m
        m = 0
print(ans)

### FIXED CODE ###

from operator import itemgetter

n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
ans = 0
a.sort(key=itemgetter(0))
i = 0
while(1):
    if m == 0:
        break
    if a[i][1] <= m:
        ans += a[i][0]*a[i][1]
        m -= a[i][1]
        i += 1
    else:
        ans += a[i][0]*m
        m = 0
print(ans)
### BUGGY CODE ###

#C - Sum of product of pairs
N = int(input())
A = list(map(int,input().split()))
SUM = 0
MOD = 1000000007
for i in range(N-1):
    for j in range(i+1,N):
            SUM = (SUM + (A[i] * A[j] % MOD) ) % MOD

# 出力
print(SUM)


### FIXED CODE ###

#C - Sum of product of pairs
N = int(input())
A = list(map(int,input().split()))
SUM = 0
jsum= 0
MOD = 1000000007
for j in range(N):
    jsum = (jsum + A[j]) % MOD

for i in range(N-1):
    jsum = (jsum - A[i]) % MOD
    SUM = ( SUM + (jsum * A[i] % MOD ) ) % MOD

# 出力
print(SUM)
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
c = 1
for i in range(N):
    d = c*A[i]
    if i >= K:
        d //= A[i-K]
        if d > c:
            print("Yes")
        else:
            print("No")
    c = d


### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for i in range(N):
    if i >= K:
        if A[i] > A[i-K]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

n=int(input())
count=0
for i in range(1,n):
    for t in range(1,n):
        if n-i*t>0:
            count +=1
        else:
            pass
print(count)

### FIXED CODE ###

from sys import stdin
input=stdin.readline
n=int(input().rstrip())
count=0
for i in range(1,n):
    
    for t in range(1,n):
        if n-i*t>0:
            count +=1
        else:
            break
print(count)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())
    
dic = {}
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]]=s.count(s[i])
    
ans = sorted([k for k, v in dic.items() if v == max(dic.values())])

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

import collections
n = int(input())
s = []
for i in range(n):
    s.append(input())
    
dic = collections.Counter(s)
dic = dic.most_common()

ans = [dic[0][0]]

for i in range(len(dic)-1):
    if dic[i][1] == dic[i+1][1]:
        ans.append(dic[i+1][0])
    else:
        break
        
ans = sorted(ans)

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

A,B = map(int, input().split())

if A > B:
  tmp = B
  B = A
  A = tmp
  
i = 1
while True:
  if (A*i) % B == 0:
    print(A*i)
    break

### FIXED CODE ###

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

import fractions

print(int(a*b/fractions.gcd(a,b)))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

for l in range(k):
    if a==[n]*n: 
        break
    left_right = [(max(0,i-a[i]), min(n-1,i+a[i]) ) for i in range(n)]
#    print(left_right)
    a=[0]*n
    for i in range(n):
        for j in range(left_right[i][0], left_right[i][1]+1 ):
            a[j]+=1
#     a = [ sum(left_right[j][0]<=i<=left_right[j][1] for j in range(n)) for i in range(n)]

print(*a) 

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

for l in range(k):
    if a==[n]*n: 
        break
    imos = [0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i]) ]+=1
        imos[min(n-1,i+a[i])+1 ]-=1

    a=[0]*n
    a[0]=imos[0]
    for i in range(1,n):
        a[i] = a[i-1]+imos[i]

print(*a)
### BUGGY CODE ###

n = int(input())
i = 1
while i <= n:
 if i % 3 == 0:
  print(' {0}'.format(i))
  continue
 elif i % 10 == 3:
  print(' {0}'.format(i))
  continue
 i += 1

### FIXED CODE ###

n = int(input())
i = 1
for i in range(1, n + 1):
 if i % 3 == 0:
  print(' {0}'.format(i), end = '')
 else:
  st = str(i)
  for x in range(0, len(st)):
   if st[x] == '3':
    print(' {0}'.format(i), end = '')
    break
print()
### BUGGY CODE ###

import math

N = int(input())
S = ["".join(sorted(input())) for i in range(N)]

S_ = set(S)

a = [math.factorial(S.count(i)) // (math.factorial(S.count(i) - 2) * math.factorial(2)) for i in S_ if not S.count(i) == 1]

print(int(sum(a)))


### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
existed = {}
c = 0
for i in range(n):
  sorted_s = ''.join(sorted(s[i]))

  if sorted_s in existed:
    c += existed[sorted_s]
    existed[sorted_s] += 1
  else:
    existed[sorted_s] = 1
print(c)
### BUGGY CODE ###

def e(dice):
    return sum([r / dice for r in range(1, dice+1)])

n, k = map(int, input().split())
P = list(map(e, (map(int, input().split()))))

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(P[i:i+k]))
print(ans)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from itertools import accumulate

    def e(dice):
        ans = 0
        for r in range(1, dice+1):
            ans += r /dice
        return ans

    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    p_cum = [0] + list(accumulate(p))

    ma = 0
    ind = 0
    for i in range(k, n+1):
        temp = p_cum[i] - p_cum[i-k]
        if ma < temp:
            ma = temp
            ind = i

    x = p[ind-k:ind]

    print(sum(e(d) for d in x))

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

import sys
X = list(sys.stdin.readline().strip())
N = len(X)

def solve():
    cnt = 0
    i = 0
    while True:
        while i < N and X[i] != 'S':
            i += 1
        j = i
        while j < N and X[j] != 'T':
            j += 1
        if j == N:
            return N - 2*cnt
        cnt += 1
        X[i] = ' '
        X[j] = ' '
        i += 1
        j += 1

print(solve())

### FIXED CODE ###

X = list(input())
N = len(X)
NHALF = N // 2

def solve():
    nt, ns = 0, 0
    for i in range(N):
        if X[i] == 'S':
            ns += 1
        elif ns > 0:
            ns -= 1
        else:
            nt += 1
    return nt + ns


print(solve())
### BUGGY CODE ###

from collections import deque
from collections import defaultdict
from collections import Counter
from itertools import permutations

def main():
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    for l, r in LR:
        cnt = 0
        for i in range(l, r + 1, 2):
            x = (i + 1) // 2
            if is_prime(i) and is_prime(x):
                cnt += 1
        print(cnt)

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

main()


### FIXED CODE ###

import bisect

def main():
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    l = min(LR)[0]
    r = max(LR, key=lambda x: x[1])[1]
    num = []
    apnd = num.append
    for i in range(l, r + 1, 2):
        x = (i + 1) // 2
        if is_prime(i) and is_prime(x):
            apnd(i)

    for l, r in LR:
        x = bisect.bisect_left(num, l)
        y = bisect.bisect_right(num, r)
        print(y - x)

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

main()
### BUGGY CODE ###

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

ans = 1
for i in l:
  ans *= i
if ans >10**18:
  print('-1')
else:
  print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in l:
  print(0)
else:
  for i in l:
    ans *= i
    if ans >10**18:
      break
  
  if ans >10**18:
    print('-1')
  else:
    print(ans)
### BUGGY CODE ###

N = int(input())

A = []

for i in range(N):
	b= input()
	if b == "deleteFirst":
		A.pop(0)
	elif b == "deleteLast":
		A.pop()
	else:
		b, c = b.split()
		c = int(c)
	
		if b == "insert":
			A.insert(0, c)
		elif b == "delete":
			if (c in A):
				A.remove(c)

print(" ".join(map(str, A)))
	

### FIXED CODE ###

from collections import deque

N = int(input())

A = deque()

for i in range(N):
	b= input()
	if b == "deleteFirst":
		A.popleft()
	elif b == "deleteLast":
		A.pop()
	else:
		b, c = b.split()
		c = int(c)
	
		if b == "insert":
			A.appendleft(c)
		elif b == "delete":
			if (c in A):
				A.remove(c)

print(" ".join(map(str, A)))
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = int(S(), 2)
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
cnt = [0] * len(D)
ans = 0
for k in range(len(D)):
    bit = x >> (n - D[k])
    r_bit=(1<<D[k])-1^bit
    cnt[k] = (cnt[k] + bit) % mod
    m = 0
    for i in range(n // D[k]):
        m <<= D[k]
        if i % 2:
            m |= r_bit
        else:
            m |= bit
    if m <= x:
        cnt[k] += 1
    ans += cnt[k] * D[k] * 2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
    ans %= mod

print(ans % mod)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
bx=int(x,2)
cnt = [0] * len(D)
ans = 0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(int(f,2)<=bx)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod
    ans %= mod

print(ans % mod)
### BUGGY CODE ###

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

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

candidate = []
candidate.extend(A)

for j in range(M):
    b, c = map(int, input().split())    
    candidate.extend([c] * b)        
    candidate = sorted(candidate, reverse=True)[:N]
        
print(sum(candidate))

### FIXED CODE ###

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

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

BC = []

for j in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
sorted_BC = sorted(BC, reverse=True, key=lambda item: item[1])

candidate = []
count = N
for bc in sorted_BC:
    b = bc[0]
    c = bc[1]
    if count >= 0:
        candidate.extend([c] * b)
        count = count - b
    else:
        break
    
candidate.extend(A)

print(sum(sorted(candidate, reverse=True)[:N]))