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

N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= 2 ** (N-1-i) % one_pop
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += 2 ** (N-1-i) % zero_pop
        x %= zero_pop
    
    print(f_count(x) + 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[-1])



### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[-1])
### BUGGY CODE ###

n = int(input())
mod = 10**23 + 117

d = {}

S = [input() for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)



### FIXED CODE ###

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

n = int(input())
mod = 10**23 + 117

d = {}

S = [input()[:-1] for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)
### BUGGY CODE ###


"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
cut = min(K-2, N*M-K)
# このfor文は少ないほうが良い
for i in range(num,1,-1):
    if num-i == cut:
        break
    fa *= i
pat = fa//factorial(cut)

# print(pat)
# xi-xj
n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)

### FIXED CODE ###


"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
# フェルマーの小定理をつかって、mod(M)でのcombinationが高速で求まる
# http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
def mod_combination(n,r,mod):
    if n<0 or r<0 or n<r:
        return 0
    if n==0 or r == 0:
        return 1
    a = factorial(n) % mod
    b = factorial(r) % mod
    c = factorial(n-r) % mod
    return (a*pow(b,mod-2,mod)*pow(c,mod-2,mod)) % mod 

pat = mod_combination(N*M-2,K-2,mod)

n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)
### BUGGY CODE ###

from itertools import combinations
from collections import Counter

N = int(input())
S = input()
ans = 0
for i, j in combinations(range(N-1), 2):
    if S[i] == S[j]: continue
    l = j - i
    temp = set([S[i], S[j]])
    if 'R' not in temp: key = 'R'
    elif 'G' not in temp: key = 'G'
    else: key = 'B'
    counter = Counter(S[j+1:j+l] + S[j + l + 1:])
    ans += counter[key]
print(ans)

### FIXED CODE ###

from itertools import combinations

N = int(input())
S = input()
counter_R = [0]
counter_G = [0]
counter_B = [0]
for s in S:
    counter_R.append(counter_R[-1] + (s == 'R'))
    counter_G.append(counter_G[-1] + (s == 'G'))
    counter_B.append(counter_B[-1] + (s == 'B'))
ans = 0
for i, j in combinations(range(N-1), 2):
    if S[i] == S[j]: continue
    l = j - i
    temp = [S[i], S[j]]
    if 'R' not in temp: cnt = counter_R
    elif 'G' not in temp: cnt = counter_G
    else: cnt = counter_B
    if j + l > N:
        ans += cnt[-1] - cnt[j]
    else:
        ans += cnt[j+l] - cnt[j] + (cnt[-1] - cnt[j + l + 1] if j + l + 1 <= N else 0)
print(ans)
### BUGGY CODE ###

ans = 0
c = [0] * 100000
n = int(input())
a = [int(input()) for i in range(n)]
s = set(a)
for i in s:
    if a.count(i) % 2 == 1:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter([input() for i in range(n)])
print(len([x for x in a.values() if x % 2 == 1]))
### BUGGY CODE ###

INF=10**30
N=int(input())
A=list(map(int,input().split()))
dp=[[-INF for i in range(16001)] for i in range(N+1)]
dp[0][0]=1000#dp[i][j]=i日目に株をj個持っているときの最大所持金

for i in range(N):
    for j in range(16001):
        if dp[i][j]==-INF:
            continue
        for x in range(j+1):#買う
            if j-x>=0:
                dp[i+1][j-x]=max(dp[i][j]+A[i]*x,dp[i+1][j-x])
            else:
                break
        for x in range(dp[i][j]//A[i]+1):#売る
            if dp[i][j]-A[i]*x>=0:
                dp[i+1][j+x]=max(dp[i][j]-A[i]*x,dp[i+1][j+x])
            else:
                break
print(max(dp[N]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
money=1000;kabu=0
i=0
while(i<N):
    j=i
    money,kabu=money-(money//A[i])*A[i],kabu+(money//A[i])
    while(j<N-1 and A[j]<=A[j+1]):
        j+=1
    money=money+kabu*A[j]
    kabu=0
    i=j+1
print(money)
### BUGGY CODE ###

INF = 10**9

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

dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    l = min([i, k])
    a = INF
    hsi = hs[i]
    for m in range(1, l + 1):
        v = dp[i - m] + abs(hs[i - m] - hsi)
        if a > v:
            a = v
    dp[i] = a
print(dp[-1])


### FIXED CODE ###

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

hs = list(map(int, input().split(' ')))

dp = [float('inf')] * (n + k + 1)
dp[0] = 0

for i in range(n - 1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min([
                dp[i + j],
                dp[i] + abs(hs[i] - hs[i + j])
            ])

print(dp[n - 1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,Q=[int(x) for x in input().strip().split()]
S=input().strip()

for _ in range(Q):
    l,r=[int(x) for x in input().strip().split()]
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,Q=[int(x) for x in input().strip().split()]
S=input().strip()
n=[]
cnt=0
p=''
for s in S:
    if p=='A' and s =='C':
        cnt+=1
        p=''
    else:
        p=s
    n.append(cnt)

for _ in range(Q):
    l,r=[int(x) for x in input().strip().split()]
    ans = n[r-1]-n[l-1]
    print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(a,b,c):
    d = math.gcd(a,b)
    return math.gcd(d,c)
cnt =0
L =[]
K = int(input())
for i in range(1,K+1):
    for m in range(1,K+1):
        for u in range(1,K+1):
            L.append(gcd(i,m,u))
print(sum(L))

### FIXED CODE ###

import math
K = int(input())

def gcd(a,b):
    return math.gcd(a,b)
cnt=0
for i in range(1,K+1):
    for m in range(1,K+1):
        d = math.gcd(i,m)
        for u in range(1,K+1):
            cnt+=math.gcd(d,u)
            
print(cnt)
### BUGGY CODE ###

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

B=[0]*N
c=0

for i in range(N-1):
    for j in range(i+1,N):
      B[j]=A[i]*A[j]
      c=(c+B[j])%(10**9+7)
print(c)

### FIXED CODE ###

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

c=0
for i in range(N):
    c=c+A[i]**2
    
print((sum(A)**2-c)//2%(10**9+7))
### BUGGY CODE ###

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

d=60
dp=[[-1]*n for i in range(d+1)]
for i,aa in enumerate(a):
  dp[0][i]=aa-1
for i in range(d):
  for j in range(n):
    dp[i+1][j]=dp[i][dp[i][j]]
ans=0
for i in range(d):
  if k&(1<<i):
    ans=dp[i][ans]
print(ans+1)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[]
o=(n+1)*[-1]
cycle,l=1,0
v=1
while o[v]==-1:
  o[v]=len(visited)
  visited.append(v)
  v=a[v-1]
cycle=len(visited)-o[v]
l=o[v]
if k<l:
  print(visited[k])
else:
  k-=l
  k%=cycle
  print(visited[l+k])
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k]:
        ans+=1
      else:
        break
print(ans)
      
        
        


### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ans=0
ans1=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+ans1,n):
      ans1=0
      if l[i]+l[j]>l[-1]:
        ans+=n-j-1
        break
      elif l[i]+l[j]<=l[k] :
        ans+=k-j-1
        ans1+=k-j-1
        break
      
      
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import itertools

"""
(a_i+1,a_{i+1}] に x がある間は...使う。傾き-1
a_{i+1} -> a_{i+1} + 1 のところでがくっと下がる
そこからa_iまでは傾き0
""" 

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
FROM = A[:-1]
TO = A[1:]

d_slope = [0] * (M+1) # 傾きの差分

"""
5,4,3,2,1,5,5,5,5
0,-1,-1,-1,-1,4,0,0,0
0,-1,0,0,0,0,5,-4,0,0
"""

for x,y in zip(FROM,TO):
    if y < x:
        y += M
    z = y - x
    if z == 1:
        continue
    d_slope[1+(x+1)%M] += -1
    d_slope[1+y%M] += z # 1回で行けたのがz回かかるようになる
    d_slope[1+(y+1)%M] += 1-z

slope = list(itertools.accumulate(d_slope))
slope = [x - sum(slope)//M for x in slope]
slope[0] = 0

# 1番をお気に入りにしたときのスコアを求める
cnt = 0
for x,y in zip(FROM,TO):
    if x < y:
        cnt += (y-x)
    else:
        cnt += y

cnt

answer = cnt + min(itertools.accumulate(slope[2:]))
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools

"""
(a_i+1,a_{i+1}] に x がある間は...使う。傾き-1
a_{i+1} -> a_{i+1} + 1 のところでがくっと下がる
そこからa_iまでは傾き0
""" 

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
FROM = A[:-1]
TO = A[1:]

d_slope = [0] * (M+1) # 傾きの差分

"""
5,4,3,2,1,5,5,5,5
0,-1,-1,-1,-1,4,0,0,0
0,-1,0,0,0,0,5,-4,0,0
"""

for x,y in zip(FROM,TO):
    if y < x:
        y += M
    z = y - x
    if z == 1:
        continue
    d_slope[1+(x+1)%M] += -1
    d_slope[1+y%M] += z # 1回で行けたのがz回かかるようになる
    d_slope[1+(y+1)%M] += 1-z

slope = list(itertools.accumulate(d_slope))
S = sum(slope)
slope = [x - S//M for x in slope]
slope[0] = 0

# 1番をお気に入りにしたときのスコアを求める
cnt = 0
for x,y in zip(FROM,TO):
    if x < y:
        cnt += (y-x)
    else:
        cnt += y

answer = cnt - slope[1] + min(itertools.accumulate(slope[1:]))
print(answer)
### BUGGY CODE ###

s = input()
t = input()

u = ""
while len(u) < len(s) + len(t):
    u = s * (len(t) // len(s) + 1)

t_add = t + "."


def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table


table_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)


### FIXED CODE ###

s = input()
t = input()

u = s * (len(t) // len(s) + 2)

t_add = t + "."


def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table


table_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)
### BUGGY CODE ###

import math
def main():
    N, M = map(int, input().split())
    S = input()
    T = input()

    L = (N * M) // math.gcd(N, M)
    good = [-1 for i in range(4 * L)]

    idx_s = 0
    idx_t = 0

    idx = 0
    for i in range(1, N + 1):
        idx = (i - 1) * (L // N) + 1
        good[idx] = S[idx_s]
        idx_s += 1

    idx = 0
    for i in range(1, M + 1):
        idx = (i - 1) * (L // M) + 1

        if i == 1:
            if good[idx] != T[idx_t]:
                print(-1)
                exit()
            else:
                idx_t += 1

        else:
            if good[idx] == -1 or good[idx] == T[idx_t]:
                good[idx] = T[idx_t]
                idx_t += 1
            else:
                print(-1)
                exit()
    
    max_idx = max(((N - 1) * (L // N) + 1), ((M - 1) * (L // M) + 1))
    r, m = divmod(max_idx, L)

    ans = 0
    if m == 0:
        ans = r * L
    else:
        ans = (r + 1) * L

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
def main4():
    N, M = map(int, input().split())
    S = input()
    T = input()

    L = (N * M) // math.gcd(N, M)

    pair = dict()

    for i in range(1, N + 1):
        idx = (i - 1) * (L // N) + 1
        pair[idx] = S[i - 1]

    for i in range(1, M + 1):
        idx = (i - 1) * (L // M) + 1

        if idx in pair.keys():
            if pair[idx] != T[i - 1]:
                print(-1)
                exit()

    print(L)

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

import heapq

n = int(input())
a = list(map(int, input().split()))
ans = []
ha = a[:]
heapq.heapify(ha)

for _ in range(n):
    minA = heapq.heappop(ha)
    ans.append(a.index(minA)+1)
print(*ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = list(range(n))
a_ = []
ans = []
for _a, _l in zip(a, l):
    a_.append([_a, _l+1])
a_.sort()

for i in range(n):
    ans.append(a_[i][1])
print(*ans)
### BUGGY CODE ###

# coding: utf-8
S=list(input())
Q=int(input())
re=1
for i in range(Q):
    q=input()
    if q=="1":
        re*=-1
    else:
        two,F,C=q.split()
        if re==1:
            if F=="1":
                S.insert(0,C)
            else:
                S.append(C)
        else:
            if F=="2":
                S.insert(0,C)
            else:
                S.append(C)

if re==-1:
    S.reverse()

ans="".join(S)
print(ans)



### FIXED CODE ###

# coding: utf-8
from collections import deque
S=list(input())
Q=int(input())
Sque=deque(S)
re=1
for i in range(Q):
    q=input()
    if q=="1":
        re*=-1
    else:
        two,F,C=q.split()
        if re==1:
            if F=="1":
                Sque.appendleft(C)
            else:
                Sque.append(C)
        else:
            if F=="2":
                Sque.appendleft(C)
            else:
                Sque.append(C)
S=list(Sque)
if re==-1:
    S.reverse()

ans="".join(S)
print(ans)
### BUGGY CODE ###

X=int(input())
place=[]
time=1
place.append(0)
while True:
	next=[]
	for i in place:
		if i+time not in place:
			next.append(i+time)
		if i-time not in place:
			next.append(i+time)
	if X in next:
		break
	time+=1
	place.extend(next)
print(time)

### FIXED CODE ###

X=int(input())
place=0
time=0
while place<X:
	time+=1
	place+=time
print(time)
### BUGGY CODE ###

def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(m):
        a, b = map(int, input().split())
        for __ in range(a):
            A.append(b)
    A.sort(reverse=True)
    print(sum(A[0:n]))
resolve()

### FIXED CODE ###

def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    B=[]
    ans=0
    k=0
    j=0
    for _ in range(m):
        a, b = map(int, input().split())
        B.append([b,a])
    for i in A:
        B.append([i,1])
    B.sort(reverse=True)
    f=B[0][1]
    while f<n:
        k+=B[j][1]
        f+=B[j+1][1]
        ans+=B[j][0]*B[j][1]
        j+=1
    ans+=B[j][0]*(n-k)

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

def main():

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

    K = 5*10**6
    INF = 10**18
    dp = [[-INF]*K for i in range(n+1)]
    dp[0][0] = 1000
    for i in range(n):
        for j in range(K):
            dp[i+1][j] = dp[i][j]
        # sell
        for j in range(K):
            if j == 0:
                continue
            if dp[i][j] >= 0:
                #if i == 2 and j == 10:
                    #print(dp[i+1][0], dp[i][j]+j*A[i])
                dp[i+1][0] = max(dp[i+1][0], dp[i][j]+j*A[i])
                #if i == 2 and j == 10:
                    #print(dp[i+1][0])

        # buy
        for j in range(K):
            if dp[i][j] >= 0:
                q, r = divmod(dp[i][j], A[i])
                dp[i+1][q] = max(r, dp[i+1][q])
    #print(dp[1])
    ans = -INF
    for j in range(K):
        ans = max(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():

    n = int(input())
    A = list(map(int, input().split()))
    INF = 19**18

    X = []
    Y = []
    A = [INF] + A
    for i in range(1, n):
        if len(X) == len(Y):
            if A[i-1] >= A[i] and A[i] < A[i+1]:
                X.append(i)
        if len(X) > len(Y):
            if  A[i-1] <= A[i] and A[i] > A[i+1]:
                Y.append(i)
    else:
        if len(X) > len(Y):
            Y.append(i+1)
    #print(X)
    #print(Y)

    cur = 1000
    for i, j in zip(X, Y):
        q, cur = divmod(cur, A[i])
        cur += q*A[j]
    print(cur)



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

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r.sort()
G = [[10**9 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a,b,c = map(int,input().split())
    G[a][b] = min(G[a][b],c)
    G[b][a] = G[a][b]
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(G)
import itertools
ans = 10**9
for v in itertools.permutations(r):
    v = list(v)
    a = 0
    s = v.pop(0)
    for i in range(R-1):
        t = v[i]
        a += G[s][t]
        s = t
    ans = min(a,ans)
print(ans)

### FIXED CODE ###

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r.sort()
G = [[10**9 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a,b,c = map(int,input().split())
    G[a][b] = min(G[a][b],c)
    G[b][a] = G[a][b]
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
warshall_floyd(G)
import itertools
ans = 10**9
for v in itertools.permutations(r):
    v = list(v)
    a = 0
    s = v.pop(0)
    for i in range(R-1):
        t = v[i]
        a += G[s][t]
        s = t
    ans = min(a,ans)
print(ans)
### BUGGY CODE ###

N = int(input())
HPs = list(map(int,input().split()))
while True:
    min_hp = min(HPs)
    for i in range(len(HPs)):
        if i == HPs.index(min_hp):
            continue
        HPs[i] = HPs[i] % min_hp
    for j in range(HPs.count(0)):
        if HPs.count(0)==len(HPs):
            print(HPs[0])
            exit()
        HPs.remove(0)
    if len(HPs)==1:
        break

print(HPs[0])


### FIXED CODE ###

from fractions import gcd
N = int(input())
HPs = list(map(int,input().split()))
ans = HPs[0]
for i in HPs:
    ans = gcd(ans,i)
print(ans)