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

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])


### FIXED CODE ###

from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
ans = int(dp[0][-1])
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 1000000007

C = [[0 for _ in range(4005)] for _ in range(4005)]
C[0][0] = 1
for i in range(4000):
  for j in range(4000):
    C[i + 1][j] += C[i][j] % MOD
    C[i + 1][j + 1] += C[i][j] % MOD

def comb(n, k):
  return C[n][k]

def f2(n, k):
  return comb(n + k - 1, k - 1)

def f(n, k):
  if n < k:
    return
  if n == 0 and k == 0:
    return 1
  if k < 1:
    return 0
  return f2(n - k, k)

for i in range(1, K + 1):
  blue = f(K, i)
  red = (f(N - K, i - 1) + 2 * f(N - K, i) + f(N - K, i + 1)) % MOD
  ans = blue * red
  print(ans % MOD)

### FIXED CODE ###

N, K = map(int, input().split())
MOD = 1000000007

fact = [1]
for i in range(1, N):
  fact.append(fact[-1] * i)

def comb(n, k):
  return (fact[n] // (fact[n - k] * fact[k])) % MOD

def f2(n, k):
  return comb(n + k - 1, k - 1)

def f(n, k):
  if n < k:
    return 0
  if n == 0 and k == 0:
    return 1
  if k < 1:
    return 0
  return f2(n - k, k)

for i in range(1, K + 1):
  blue = f(K, i)
  red = (f(N - K, i - 1) + 2 * f(N - K, i) + f(N - K, i + 1)) % MOD
  ans = blue * red
  print(ans % MOD)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(sorted(map(int, input().split()), key=lambda x: -x))

for _ in range(M):
    A[0] /= 2

    p = 0
    while p < N - 1 and A[p] < A[p + 1]:
        A[p], A[p + 1] = A[p + 1], A[p]
        p += 1

print(sum(map(int, A)))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x: -1 * int(x), input().split()))

heapq.heapify(A)
for _ in range(M):
    a = -1 * heapq.heappop(A)
    a //= 2
    heapq.heappush(A, -1 * a)

print(-1 * sum(A))
### BUGGY CODE ###

import numpy as np
from collections import Counter


n = int(input())
a = [int(x) for x in input().split(' ')]

s = np.array(sorted(set(a)),int)
i = 1
while i < len(s)-1:
    s = np.concatenate([s[:i], s[i:][s[i:]%s[i-1]!=0]],0)
    i += 1
s = set(s)

c = Counter(a)
keys = set([k for k, v in c.items() if v == 1])

print(len(s&keys))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]

a.sort()
a_max = a[-1] + 1   # aの最大値
lst = [0] * a_max   # a_max個のリストを生成

for x in a:
    lst[x] += 1                         # リストの該当の数字に1追加 
    if lst[x] == 1:                     # まだ他の数値の倍数でなければ、リストへ2倍、3倍…の数字を1追加していく
        for i in range(x*2, a_max, x):
            lst[i] += 1

output = 0
for x in a:
    if lst[x] == 1:
        output += 1
print(output)
### BUGGY CODE ###

K = int(input())

res = -1
count = 0
ai = 0
while(True):
    ai = (ai*10 + 7) % K
    count += 1
    if(ai == 0):
        res = count
        break

print(res)


### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

res = -1
count = 0
ai = 0
while(True):
    ai = (ai*10 + 7) % K
    count += 1
    if(ai == 0):
        res = count
        break

print(res)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = np.array(list(map(int,input().split())))
maxim = max(A)
select_num = 0
count_num = np.array([0]*(maxim+1))
for i in range(1,maxim+1):
  temp = np.count_nonzero(A == i)
  count_num[i] = temp
  select_num += (temp)*(temp - 1)//2
for i in A:
  print(select_num -count_num[i] + 1)

### FIXED CODE ###

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

select_num = 0
count_num = [0]*(N+1)
for i in A:
  count_num[i] += 1
for i in range(1,N+1):
  select_num += (count_num[i])*(count_num[i] - 1)//2
for i in A:
  print(select_num -count_num[i] + 1)
### BUGGY CODE ###

import fractions


k = int(input())

def gcd(p, q):
    if p % q == 0: return q
    return gcd(q, p % q)

res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            res += gcd(gcd(a, b), c)
print(res)



### FIXED CODE ###

import fractions


k = int(input())

def gcd(p, q):
    if p % q == 0: return q
    return gcd(q, p % q)

res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            res += gcd(gcd(a, b), c)
print(res)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)-3):
    for j in range(i+3, len(s)):
        x = int(s[i:j+1])
        if x %2019 == 0:
            ans += 1
            j += 3
            if j > len(s)-1:
                break
print(ans)

### FIXED CODE ###

import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque

n=int(input())
a=[0]*n

for i in range(n):
  a[i]=deque(list(map(lambda x:int(x)-1,input().split())))

  
q=deque([])
for idx,i in enumerate(a):
  x=idx
  y=i[0]
  if x == a[y][0]:
    if x not in q and y not in q:
      q.append(x)
      q.append(y)
      a[x].popleft()
      a[y].popleft()

      
day=0
while True:
  day+=1
  t=deque([])
  while q:
    t.append(q.popleft())
  while t:
    i=t.popleft()
    if len(a[i])==0: continue;
    #print(f'i={i},a[i][0]={a[i][0]}')
    j=a[i][0]
    if len(a[j])==0: continue;
    if i == a[j][0] and i not in q and j not in q:
      q.append(i)
      q.append(j)
      a[i].popleft()
      a[j].popleft()
  
  #print(f'a={a}')
  if len(q)==0: break;


for i in range(n):
  if len(a[i])!=0:
    print(-1)
    exit()
print(day)
    


### FIXED CODE ###

from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      exit()
  print(day)


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

def main():
    n=int(input())
    s=input()
    r = [0]*n
    g = [0]*n
    b = [0]*n
    ans = 1

    dict = {"R":r, "G":g, "B":b}

    for i in range(n):
        dict[s[i]][i] = 1
    
    for l in dict.values():
        ans *= sum(l)
 
    for i in range(n):
        for j in range(i,n):
            if dict[s[i]][j] == 0:                
                s1 = s[i]
                s2 = s[j]
                t = (s1,s2)
                for s3 in "RGB":
                    if s3 not in t:
                        if 2*j-i < n and dict[s3][2*j-i] == 1:
                            ans -= 1

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    ans = 1

    r_cnt = s.count("R")
    g_cnt = s.count("G")

    ans = r_cnt*g_cnt*(n-r_cnt-g_cnt)
 
    for i in range(n):
        for j in range(i,n):
            s1 = s[i]
            s2 = s[j]
            if s1 != s2:
                t = (s1,s2)
                for s3 in "RGB":
                    if s3 not in t:
                        if 2*j-i < n and s[2*j-i] == s3:
                            ans -= 1
                        continue

    print(ans)

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

N = int(input())
d = [[-1 for _ in range(N)] for _ in range(N)]
e = [[] for _ in range(N)]
dd = [-1 for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    e[u-1].append(v-1)
    e[v-1].append(u-1)
    d[u-1][v-1] = d[v-1][u-1] = w

def dfs(i, _d):
    dd[i] = _d
    for c in e[i]:
        if dd[c]!=-1: continue
        dfs(c, _d+d[i][c])

dfs(0,0)
for _dd in dd:
    print(_dd%2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
d = {}
e = [[] for _ in range(N)]
dd = [-1]*N
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    e[u-1].append(v-1)
    e[v-1].append(u-1)
    d[(u-1,v-1)]= d[(v-1,u-1)] = w

def dfs(i, _d):
    dd[i] = _d
    for c in e[i]:
        if dd[c]!=-1: continue
        dfs(c, _d+d[(i,c)])

dfs(0,0)
for _dd in dd:
    print(_dd%2)
### BUGGY CODE ###

from operator import mul
from functools import reduce

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


beforePoint = reduce(mul, A[:K])

for i in range(0, N-K):
    point = (beforePoint//A[i]) * A[i+K]
    # print(beforePoint, point)
    if beforePoint < point:
        print("Yes")
    else:
        print("No")
    beforePoint = point


### FIXED CODE ###

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

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

if K>=N-1:
    print(h[N-1]-h[0])
else:
    dp = [10**10 for i in range(N)]
    dp[0] = 0
    for i in range(0, N):
        for j in range(1, K+1):
            if i>=j:
                dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
    print(dp[N-1])



### FIXED CODE ###

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

if K >= N - 1:
    print(h[N - 1] - h[0])
else:
    dp = [10 ** 10 for i in range(N)]
    dp[0] = 0
    for i in range(1, N):
        for j in range(1, K + 1):
            if i >= j:
                dp[i] = min(dp[i - j] + abs(h[i] - h[i - j]), dp[i])
    print(dp[N - 1])
### BUGGY CODE ###

import math
import itertools

from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

#def gcd_list(numbers):
#    return reduce(math.gcd, numbers)
    
N=int(input())
GCD=[]
GCD1=[]
for i in range (1,N+1):
    GCD.append(i)
#print(GCD)
for i in itertools.product(GCD,repeat=3):
    
#for i in itertools.combinations_with_replacement(GCD,3):
    GCD1.append(gcd(i[0],i[1],i[2]))
    #print(gcd(i[0],i[1],i[2]))
    #print(i)
   # print(GCD)
#print(GCD)
print(sum(GCD1))

### FIXED CODE ###

import math
import itertools
GCD_over_150=[4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692]
 
N=int(input())
if N<150:
	GCD=[]
	GCD1=[]
	for i in range (1,N+1):
		GCD.append(i)
	for i in itertools.product(GCD,repeat=3):
		GCD1.append(math.gcd(math.gcd(i[0],i[1]),i[2]))
	print(sum(GCD1))    
else:
    print(GCD_over_150[N-150])
### BUGGY CODE ###

def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  #print(S)
  
  ans = 10000
  for i in range(2**(H-1)):
    th = bin(i).count('1')
    ans0 = th
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    #print(th,T)
    tw = 0
    #for k in range(W):
    k = 0
    while(k < W):
      f = True
      #print(tw)
      for j in range(th+1):
        if sum(T[j][tw:k+1]) > K:
          f = False
        #print(sum(T[j][tw:k+1]),f,tw,k)
      if not f:
        if tw == k:
          ans0 = 10000
          break
        else:
          tw = k
          k -= 1
          ans0 += 1
      k += 1
    ans = min(ans0,ans)
  print(ans)

main()

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  #print(S)
  
  ans = 10000
  for i in range(2**(H-1)):
    # 横方向の割り方を全検索する。
    # T:横方向の割り方を固定したときに、同じブロック内のホワイトチョコの個数を縦方向に集約した配列。
    th = bin(i).count('1')
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    #print(th,T)

    # 縦方向の1列分の中に、Kより大きい個数のホワイトチョコが含まれる場合は
    # どのように割っても条件を満たさないのでスキップする。
    f = True
    for k in range(W):
      for j in range(th+1):
        if T[j][k] > K:
          f = False
    if not f:
      continue

    # 横方向に順にホワイトチョコの数を数えていき、Kを超える場合は割る回数ans0を+1する。
    ans0 = th
    T0 = [0 for _ in range(th+1)]
    for k in range(W):
      f = True
      for j in range(th+1):
        T0[j] += T[j][k]
        if T0[j] > K:
          f = False
      if not f:
        ans0 += 1
        # 割った場合は、カウントしていたホワイトチョコの数をカレントの1列分に戻す。
        for j in range(th+1):
          T0[j] = T[j][k]
    ans = min(ans0,ans)
  print(ans)

main()
### BUGGY CODE ###

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

dp = [[1] + [0]*N for i in range(N+1)]
for i in range(1, N+1):
  for j in range(1, i+1):
    dp[i][j] = dp[i-1][j-1]*(P[i-1]) + dp[i-1][j]*(1-P[i-1])

print(dp[-1][(N+1)//2])

### FIXED CODE ###

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

dp = [[1] + [0]*N for i in range(N+1)]
for i in range(1, N+1):
  for j in range(1, i+1):
    dp[i][j] = dp[i-1][j-1]*(P[i-1]) + dp[i-1][j]*(1-P[i-1])

print(dp[-1][(N+1)//2])
### BUGGY CODE ###

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n - k):
  c = sum(arr[i + 1:k + i + 1])
  d = sum(arr[i:k + i])
  if c > d:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n - k):
  if arr[i] < arr[i + k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

def mx(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[-i-1]
	return sum

def mn(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[i]
	return sum
	
def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			vmx,vmn = mx(ls,m),mn(ls,m)
			if vmx < s or vmn > s: return 0
			elif vmx == s or vmn == s: return 1
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
### BUGGY CODE ###

n = int(input())

train_list = []
for i in range(n-1):
    array = list(map(int,input().split()))
    train_list.append(array)

for i in range(n-1):
    time = 0
    for j in range(i, n-1):
        if i == j:
            time += (train_list[i][0] + train_list[i][1])
        else:
            flag = False
            p = 0
            while flag is False:
                t = train_list[j][1] + train_list[j][2] * p
                if t // time >= 1:
                    flag = True
                    time = t
                    time += train_list[j][0]
                p += ((time - t)//train_list[j][2])

    print(time)

print(0)


### FIXED CODE ###

import math
n = int(input())

train_list = []
for i in range(n-1):
    array = list(map(int,input().split()))
    train_list.append(array)


for i in range(n-1):
    time = 0
    for j in range(i, n-1):
        if i == j:
            time += (train_list[i][0] + train_list[i][1])
        else:
            if train_list[j][1] // time >= 1:
                time = train_list[j][1]
                time += train_list[j][0]
            else:
                p = math.ceil((time - train_list[j][1])/train_list[j][2])
                time = train_list[j][1] + train_list[j][2] * p
                time += train_list[j][0]
    print(time)

print(0)
### BUGGY CODE ###

n = int(input())
l = [int(i) for i in input().split()]
for i in range(n):
    answer = 0
    for j in range(n - 1):
        ans = 0
        if j == i:
            continue
        for k in range(j + 1, n):
            if k != i:
                if l[k] == l[j]:
                    ans += 1
        answer += ans
    print(answer)

### FIXED CODE ###

from collections import Counter

n = int(input())
l = [int(i) for i in input().split()]

S = Counter(l)

ans = 0
for i in S.values():
    ans += int(i * (i - 1) / 2)

for i in range(n):
    val = S[l[i]]
    print(ans - val + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    PM = [-1]*N
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1
    for i in range(N):
        LIST.append(X^bit)
        PM[i] += (X & bit == 0)*2
        bit = bit<<1

    cnt = count_ones_by_bitmask(X)
    for i in range(N):
        if LIST[i]!=0:
            TEMP[i] += LIST[i] % (cnt+PM[i])
            ANS[i] += 1

    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])


def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    X = input()
    XINT = int(X,2)
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N

    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    if cnt ==1:
        for i in  range(N):
            if X[i] == '1':
                print(0) #全てが0になる
            else:
                if i==N-1:
                    print((int(X[N-1])+1)%2+1) # 2の剰余の反転
                else:
                    print((int(X[N-1]))%2+1) # 2の剰余
        return

    p = XINT % (cnt+1)
    m = XINT % (cnt-1)
    pmod = 1
    mmod = 1
    for i in range(N):
        ANS[i] = 1
        if (X[N-i-1] == '0'):
            TEMP[i] = (p + pmod) % (cnt+1)
        else:
            TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])


def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

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

from collections import deque

s = list(input())
s = deque(s)
n = int(input())

for i in range(n):
    q = input().split()
    if q[0] == '1':
        s.reverse()
    else:
        if q[1] == '1':
            s.appendleft(q[2])
        else:
            s.append(q[2])

print(''.join(s))

### FIXED CODE ###

from collections import deque

s = list(input())
s = deque(s)
n = int(input())
dire = False

for i in range(n):
    q = input().split()
    if q[0] == '1':
        dire = not dire
    else:
        t = int(q[1])-1

        if dire ^ t:
            s.append(q[2])
        else:
            s.appendleft(q[2])
if dire:
    s.reverse()

print(''.join(s))
### BUGGY CODE ###

s = input()
n = len(s)
l = [0]*n

for i in range(n):
    for j in range(1, n):
        if s[i] == "R":
            if s[i + j] == "L":
                if j%2 == 1:
                    l[i + j - 1] += 1
                else:
                    l[i + j] += 1
                break
        elif s[i] == "L":
            if s[i - j] == "R":
                if j%2 == 1:
                    l[i - j + 1] += 1
                else:
                    l[i - j] += 1
                break
print(*l)

### FIXED CODE ###

s = input()
n = len(s)
l = [1]*n

for i in range(n - 1):
    if s[i] == s[i + 1] == "R":
        l[i + 2] += l[i]
        l[i] = 0
    if s[-i - 1] == s[-i - 2] == "L":
        l[-i - 3] += l[-i - 1]
        l[-i - 1] = 0

print(*l)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = [-(int(i)) for i in input().split()]

for _ in range(m):
    b, c = map(int, input().split())
    a += ([-c] * b)

heapq.heapify(a)

ans = 0

for _ in range(n):
    ans += heapq.heappop(a)

print(-ans)

### FIXED CODE ###

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

bc = []

for _ in range(m):
    b, c = map(int, input().split())
    bc.append((b, c))

bc = sorted(bc, key=lambda x: x[1], reverse=True)

cnt = 0

for b, c in bc:
    cnt += b
    a += [c] * b
    if cnt >= n:
        break

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