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

from bisect import bisect_left


def main():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr.sort()
    s = 0

    bc = [list(map(int, input().split())) for _ in range(m)]
    bc.sort(key=lambda x: x[1], reverse=True)

    for b, c in bc:
        idx = bisect_left(arr, c)

        if b >= idx:
            s += sum(arr[b:])
            arr = [c] * idx + arr[idx:b]
        else:
            s += sum(arr[idx:])
            arr = arr[b:idx] + [c] * b

    print(s + sum(arr))


main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    s = 0

    bc = [list(map(int, input().split())) for _ in range(m)]
    bc.sort(key=lambda x: x[1], reverse=True)

    arr = []
    sum_b = 0
    for b, c in bc:
        arr += [c] * b
        sum_b += b
        if sum_b >= n:
            break

    arr += a
    arr.sort(reverse=True)
    print(sum(arr[:n]))


main()
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
Y1 = Y[:N//2]
Y2 = Y[N//2:]
ans1 = Y1[-1]
ans2 = Y2[0]
for i in range(N):
  if X[i] in Y1:
    print(ans2)
  else:
    print(ans1)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
Y1 = Y[:N//2]
Y2 = Y[N//2:]
ans1 = Y1[-1]
ans2 = Y2[0]
for i in range(N):
  if X[i] <= ans1:
    print(ans2)
  else:
    print(ans1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

K, Q = map(int, input().split())
D = list(map(int, input().split()))
NXM = [list(map(int, input().split())) for _ in range(Q)]

for N, X, M in NXM:
    E = [d % M for d in D]
    cnt, tmp = 0, 0
    for e in E:
        if e > 0:
            cnt += 1
            tmp += e
    cnt *= ((N - 1) // K)
    tmp *= ((N - 1) // K)
    for i in range((N - 1) % K):
        if E[i] > 0:
            cnt += 1
            tmp += E[i]
    tmp += X % M
    print(cnt - tmp // M)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

K, Q = map(int, input().split())
D = list(map(int, input().split()))
NXM = [list(map(int, input().split())) for _ in range(Q)]

for N, X, M in NXM:
    E = [d % M for d in D]
    cnt0 = 0
    tmp0 = 0
    for e in E:
        if e > 0:
            cnt0 += 1
            tmp0 += e
    cnt = ((N - 1) // K) * cnt0
    tmp = ((N - 1) // K) * tmp0
    for i in range((N - 1) % K):
        if E[i] > 0:
            cnt += 1
        tmp += E[i]
    tmp += X % M
    print(cnt - tmp // M)
### BUGGY CODE ###

n = int(input())

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

m = int(input())

for i in range(m):
    a,b = map(int, input().split())
    
    l = [b if j == a else j for j in l]

    print(sum(l))

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr: #あらかじめ各Aiの個数を数えておく
 cnt[val]+=1
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
 b,c=map(int,input().split())
 diff=(c-b)*(cnt[b]) #各クエリにおいて数列Aの総和は(値がBiである要素の個数)*(Ci-Bi)だけ変化する
 sums+=diff
 print(sums) 
 cnt[c]+=cnt[b] #値がCi,Biである要素の個数を更新する
 cnt[b]=0
### BUGGY CODE ###

import sys
from copy import deepcopy
F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
A_order = list(set(deepcopy(A)))
A_order.sort()

compressed_A = [None] * (N + 1)
for i in range(N + 1):
    compressed_A[i] = A_order.index(A[i])

maxA = len(A_order)
bit = [0] * (maxA + 1)
total_inversion = 0
for a in compressed_A:
    b = a + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    #total sum
    upper = maxA + 1
    upper_sum = 0
    while upper > 0:
        upper_sum += bit[upper - 1]
        upper -= upper & -upper

    #lower sum
    lower = a + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += upper_sum - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)

### FIXED CODE ###

import sys
from copy import deepcopy

F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
A_order = {0}
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
    A_order |= {A[a+1]}
maxA = len(A_order)
A_order = list(A_order)
A_order.sort()

compressed_A = dict()
for i in range(maxA):
    compressed_A[A_order[i]] = i

bit = [0] * (maxA + 1)
total_inversion = 0
for i in range(N+1):
    b = compressed_A[A[i]] + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    #lower sum
    lower = compressed_A[A[i]] + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += i + 1 - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)
### BUGGY CODE ###

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

arr=[]
for i in b:
  arr+=[[a.count(i),i]]

arr=sorted(arr)

d=len(b)-k
cnt=0
for i in range(d):
  cnt+=arr[i][0]
print(cnt)

### FIXED CODE ###

import collections

n,k=map(int,input().split())
a=list(map(int,input().split()))
now_k=len(set(a))
d=now_k-k
arr=collections.Counter(a).most_common()
#print(arr)
b=sorted([arr[i][1] for i in range(now_k)])
#print(b)
cnt=now_k
cnt2=0
flg=0
for i in b:
  cnt-=1
  cnt2+=i
  if cnt==k:
    print(cnt2)
    flg=1
    break
if flg==0:
  print(0)
### BUGGY CODE ###

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

maxpoint = 0
for x in range(n+1):
    t1 = (a * x) / b
    t2 = x/b
    tmp = int(t1)  - a * int(t2) 
    maxpoint = max(tmp,maxpoint)

print(maxpoint)



### FIXED CODE ###

from sys import stdin
input = stdin.readline
 
a,b,n = map(int,input().split())
maxpoint = 0
 
if b > n  :
    tmp = int((a * n) / b)  - a * int(n/b) 
    maxpoint = max(tmp,maxpoint)
else:
    k = int(n/b)*b -1
    maxpoint =  int((a * k) / b)  - a * int(k/b) 
    if b == 1:
        maxpoint = 0
 
print(maxpoint)
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []
for i in a:
    b.append(i)
    b.reverse()
c = ""
for i in b:
    c += i + " "
print(c)

### FIXED CODE ###

n = int(input())
a = input().split()
b = []
ans = []
even = a[1::2]
odd = a[0::2]
b.append(even)#even number
b.append(odd)#odd number
# print(b)
if len(a) % 2 == 0:
    for i in range(1,len(even) + 1):
        ans.append(even[-i])
    ans = ans + odd
else:
    for i in range(1,len(odd) + 1):
        ans.append(odd[-i])
    ans = ans + even
for i in range(len(ans)):
    if i != len(ans) -1:
        print(ans[i],end=" ")
    else:
        print(ans[i])
### BUGGY CODE ###

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

for num in a:
  ans *= num
  if ans == 0: break

print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

import sys

max = 10**18

n = int(input())
a = [int(x) for x in input().split()]
if 0 in a:
  print(0)
  sys.exit()

ans = 1

for num in a:
  ans *= num
  if ans > max:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    vA = list(map(int, input().split()))
    MOD = 10**9 + 7
    BMAX = 61

    vC = [0,]*BMAX
    for a in vA:
        d = 0
        while a:
            vC[d] += a&1
            d += 1
            a >>= 1
    res = 0
    for i,c in enumerate(vC):
        x = pow(2,i) * c * (N-c) % MOD
        res = (res + x) % MOD
    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    vA = list(map(int, input().split()))
    MOD = 10**9 + 7
    BMAX = 61

    vC = [0,]*BMAX
    for a in vA:
        d = 0
        while a:
            vC[d] += a&1
            d += 1
            a >>= 1
    res = 0
    for i,c in enumerate(vC):
        x = pow(2,i) * c * (N-c) % MOD
        res = (res + x) % MOD
    print(res)


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

import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]


def main():

    S = input()
    T = input()
    len_T = len(T)
    idx = -1
    for i in range(2**len_T):
        tmp = []
        for j in range(len_T):
            if i>>j & 1:
                tmp.append(T[j])
            else:
                tmp.append('?')
        idx = max(idx, S.rfind(''.join(tmp)))
    if idx == -1:
        print('UNRESTORABLE')
    else:
        ans = list(S.replace('?','a'))
        for i,t in enumerate(T):
            ans[idx+i] = t
        print(''.join(ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

def match(s, t, lt, offset):
    for i in range(lt):
        if t[i] != s[offset+i] and s[offset+i] != '?':
            return False
    return True

def main():
    S = input()
    T = input()
    len_S = len(S)
    len_T = len(T)
    ans = list(S.replace('?','a'))
    for i in range(len_S-len_T+1):
        offset = len_S-len_T-i
        if match(S, T, len_T, offset):
            for j in range(len_T):
                ans[offset+j] = T[j]
            break
    else:
        print('UNRESTORABLE')
        exit()
    print(''.join(ans))

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

N = int(input())
S = input()
S = [s for s in S]
cnt = 0

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
R = my_index_multi(S, 'R')
G = my_index_multi(S, 'G')
B = my_index_multi(S, 'B')
for r in R:
    for g in G:
        for b in B:
            l = [r, g, b]
            l.sort()
            if (l[1]-l[0])!=(l[2]-l[1]):
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count('R')*S.count('G')*S.count('B')

for i in range(N):
    for j in range(i+1, N):
        if S[i]!=S[j]:
            k = 2*j-i
            if k < N and S[i]!=S[k] and S[j]!=S[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for j in a:
    if j >= max(a):
        print(sorted(a)[-2])
    else:
        print(max(a))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = a[:]
b.sort()

if b[n-1] == b[n-2]:
    for _ in range(n): 
        print(b[n-1])
else:
    for j in a:
        if j >= b[n-1]:
            print(b[n-2])
        else:
            print(b[n-1])
### BUGGY CODE ###

N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[0]*N
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1 or j-i ==1:
            L[j-i]+=1
        elif i <= X-1 and j >= Y-1:
            L[1+abs(X-1-i)+abs(Y-1-j)]+=1
        elif i >= X-1 and i-(X-1) > (Y-1)-i:
            L[j-i]+=1
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L[min(L1,L2)]+=1

for i in range(1,N):
    print(L[i])




### FIXED CODE ###

N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[0]*N
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1 or j-i ==1:
            L[j-i]+=1
        elif i <= X-1 and j >= Y-1:
            L[1+abs(X-1-i)+abs(Y-1-j)]+=1
        elif i >= X-1 and i-(X-1) > (Y-1)-i:
            L[j-i]+=1
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L[min(L1,L2)]+=1

for i in range(1,N):
    print(L[i])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])
print(dp[n - 1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])
print(dp[n - 1])
### BUGGY CODE ###

import numpy as np

N,M=map(int,input().split())
A = np.array(list(map(int,input().split())),dtype="int64")

A.sort()
# print(A)

for m in range(M):
	B,C=map(int,input().split())
	cnt=np.sum(A < C)
	A[:min(B,cnt)]=C
	A.sort()
	# print(A)


print( A.sum() )


### FIXED CODE ###

import numpy as np
import bisect

N,M=map(int,input().split())
A = np.array(list(map(int,input().split())),dtype="int64")

A.sort()
# print(A)
tmpD=[]

for m in range(M):
	tmpD.append(list(map(int,input().split())))

tmpD.sort(key=lambda x:x[1],reverse=True)
D = np.array(tmpD)

curB = 0
dIndex=0
for n in range(N):

	if A[n] < D[dIndex][1]:
		A[n] = D[dIndex][1]
	else:
		break

	curB+=1
	if D[dIndex][0] <= curB:
		curB=0
		dIndex+=1
		if len(D) <= dIndex:
			break

# print(A)


print( A.sum() )
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
ans2=[]
for i in range(x):
  for j in range(y):
    ans.append(a[i]+b[j])
if len(ans)>=k:
  ans.sort()
  ans.reverse()
  ans=ans[:k]
for i in range(len(ans)):
  for j in range(z):
    ans2.append(ans[i]+c[j])
ans2.sort()
ans2.reverse()
for i in range(k):
  print(ans2[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
ans2=[]
for i in range(x):
  for j in range(y):
    ans.append(a[i]+b[j])
if len(ans)>=k:
  ans.sort()
  ans.reverse()
  ans=ans[:k]
for i in range(len(ans)):
  for j in range(z):
    ans2.append(ans[i]+c[j])
ans2.sort()
ans2.reverse()
for i in range(k):
  print(ans2[i])
### BUGGY CODE ###

import sys
N,A,B=map(int,input().split())
h=[]
for i in range(N):
  h+=[int(input())] 
count=0

while True:
  h.sort(reverse=1)
  if h[0]<=0:
    print(count)
    sys.exit()
  if (h[0]/A)%1==0:
    t=int(h[0]/A)
  else:
    t=int(h[0]/A)+1
  h[0]-=A*t
  for i in range(N-1):
    h[i+1]-=B*t
  count+=t
  if h[N-1]<=-A:
    if (h[N-1]/A)%1==0:
      t=-int(h[N-1]/A)
    else:
      t=-int(h[N-1]/A)
    h[N-1]+=t*(A-B)
    for i in range(N):
      h[i]+=t*B
    count-=t

### FIXED CODE ###

import math
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
S.sort(reverse=1)
count=0

def Check(T):
  count=0
  for i in range(N):
    a=math.ceil((S[i]-B*T)/(A-B))
    if a>0:
      count+=a
    else:
      break
  if count<=T:
    return 1
  else:
    return 0

L=1
while True:
  if S[0]/B >=2**L:
    L+=1
  else:
    break

T=2**L#checkしたいナンバー。
for l in range(L,0,-1):
  if Check(T)==1:
    T-=2**(l-1)
  elif Check(T)==0:
    T+=2**(l-1)
if Check(T)==0:
  print(T+1)
else:
  print(T)
### BUGGY CODE ###

N,*M = map(int,input().split())
abc = [list(map(int,input().split())) for _ in [0]*N]
INF = 100*40*100
dp = [[[INF]*500 for _ in [0]*500] for _ in [0]*(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    a,b,c = abc[i-1]
    for j in range(410):
        for k in range(410):
            dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = min([dp[-1][M[0]*i][M[1]*i] for i in range(1,1+400//(max(M)))])
if ans == INF:ans=-1
print(ans)

### FIXED CODE ###

N,*M = map(int,input().split())
abc = [list(map(int,input().split())) for _ in [0]*N]
INF = 100*40*100
dp = [[[INF]*500 for _ in [0]*500] for _ in [0]*(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    a,b,c = abc[i-1]
    for j in range(410):
        for k in range(410):
            dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = min([dp[-1][M[0]*i][M[1]*i] for i in range(1,1+400//(max(M)))])
if ans == INF:ans=-1
print(ans)
### BUGGY CODE ###

import math

k = int(input())

g = 0

for i in range(k):
    for j in range(k):
        for l in range(k):
            y = math.gcd(i+1, j+1)
            z = math.gcd(y, l+1)
            g += z

print(g)

### FIXED CODE ###

import math
k = int(input())

sm=0
for i in range(1,k+1):
    for l in range(1,k+1):
        gcdab=math.gcd(i,l)
        for m in range(1,k+1):
            sm+=math.gcd(gcdab,m)

print(sm)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
L = Counter(A)
for i in A:
    ans = []
    L_cp = L.copy()
    L_cp[i] -= 1
    print(sum([i*(i-1)//2 for i in L_cp.values() if i >= 2]))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
L = Counter(A)
anss = {}
sum_ans = sum([i*(i-1)//2 for i in L.values() if i >= 2])
for k,v in L.items():
    anss[k] = sum_ans - (v*(v-1)//2) + ((v-1)*(v-2)//2)
for i in A:
    print(anss[i])
### BUGGY CODE ###

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

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N,M,S,T = map(int,input().split())
UVAB = [[int(x) for x in input().split()] for _ in range(M)]
U,V,A,B = zip(*UVAB)

g1 = csr_matrix((A,(U,V)), (N+1,N+1))
g2 = csr_matrix((B,(U,V)), (N+1,N+1))
d1 = dijkstra(g1, indices=S, directed=False)
d2 = dijkstra(g2, indices=T, directed=False)

d = d1 + d2 # 各頂点を両替所に選ぶ場合

d = (np.minimum.accumulate(d[::-1])[::-1]).astype(int)

answer = 10 ** 15 - d[1:]
print(*answer, sep='\n')

### FIXED CODE ###

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

import numpy as np
from heapq import heappush, heappop

N,M,S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,a,b = map(int,input().split())
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]

print(*answer, sep='\n')
### BUGGY CODE ###

from collections import deque
import sys
read = sys.stdin.readline


def main():
    n = int(read())
    V = 1001000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = set()

    for i in range(1, n + 1):
        a = list(map(int, read().rstrip().split()))
        for j in range(n - 1):
            v1 = min(i, a[j]) * 1001 + max(i, a[j])
            vlist.add(v1)
            if j == n - 2:
                break
            v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = deque()
    for v in vlist:
        if deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print(-1)
        exit()

    while len(q):
        v = q.popleft()
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print(max(d) + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.readline

n = int(read())
V = 1001000

g = [[] for _ in range(V)]
deg = [0] * V
vlist = set()

for i in range(1, n + 1):
    a = list(map(int, read().rstrip().split()))
    for j in range(n - 2):
        v1 = min(i, a[j]) * 1001 + max(i, a[j])
        v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
        vlist.add(v1)
        vlist.add(v2)
        g[v1].append(v2)
        deg[v2] += 1

d = [0] * V
check_cnt = 0
q = []
for v in vlist:
    if deg[v] == 0:
        q.append(v)

if len(q) == 0:
    print(-1)
    exit()

for v in q:
    check_cnt += 1
    for nv in g[v]:
        d[nv] = max(d[nv], d[v] + 1)
        deg[nv] -= 1
        if deg[nv] == 0:
            q.append(nv)
if check_cnt == n * (n - 1) // 2:
    print(max(d) + 1)
else:
    print(-1)
### BUGGY CODE ###

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

for k in range(m):
	a[n-1]=a[n-1]//2
	a.sort()

for i in range(n):
	ans+=a[i]

print(ans)


### FIXED CODE ###

import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


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

import sys
input = sys.stdin.readline
from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dd = defaultdict(list)
    count = 0
    for i in range(N - 1):
        ai = A[i]
        iai = i + ai
        if dd[iai] == []:
            for j in range(i + 1, N):
                if j - A[j] == iai:
                    dd[iai].append(j)
                    count += 1
        else:
            for j in dd[iai]:
                if j > i:
                    count += 1
    print(count)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (10 ** 6)
    ans = 0
    for i in range(n):
        if i - a[i] > 0:
            ans += b[i - a[i]]
        if i + a[i] < 10 ** 6:
            b[i + a[i]] += 1
    print(ans)


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

a = []
a = input().split()
N = int(a[0])
M = int(a[1])

A = input().split()
A = [int(n) for n in A]
B = [[] for i in range(M+1)]
#B = [[]]

#B[0] = A
for i in range(M+1) :
#  B.append(A)
#  B[i+1].append(A)
  B[i] = A



count_j = [int(0) for i in range(N)]

for i in range(M) :
  for j in range(N) :
    if B[i][j] == max(B[i]) :
#      print('B[i][j]', B[i][j])
      count_j[j] = count_j[j] + 1
      B[i+1][j] = B[i+1][j] // (2)     
#      B[i+1][j] = B[0][j] // (2**(count_j[j]))
#      print('count_j', count_j)
#      print('A', A)
#      print('B', B)
      break

#print('N', N)
#print('M', M)
#print('A', A)
#print('B', B)
#print('count_j', count_j)

print(sum(A))

### FIXED CODE ###

import heapq

a = []
a = input().split()
N = int(a[0])
M = int(a[1])
A = input().split()
A = [int(n) for n in A]

for i in range(N) :
  A[i] = -A[i]

heapq.heapify(A)

for i in range(M) :
  c = heapq.heappop(A)
  heapq.heappush(A, (c+1) // 2)

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

# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
ans = 1
i = 1
limit = (m / n)
while i <= limit:
    if m % i == 0 and m // i >= n:
        ans = max(ans, i)
    i += 1
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
if n == 1:
    ans = m
else:
    ans = 1
    i = 1
    limit = m / n
    while i <= limit:
        if m % i == 0 and m // i >= n:
            ans = max(ans, i)
        i += 1
print(ans)
### BUGGY CODE ###

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

k=len(bin(max(l)))-2

for i in range(n):
    l[i]=bin(l[i])[2:]

ll=[[0,0] for i in range(k)]
for i in range(n):
    for j in range(k):
        try:
            if l[i][-1-j]=="1":
                ll[j][1]+=1
            if l[i][-1-j]=="0":
                ll[j][0]+=1
        except IndexError:
            ll[j][0]+=1

m=0
for i in range(k):
    m+=ll[i][0]*ll[i][1]*(2**i)
print(m%(10**9+7))


### FIXED CODE ###

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

k=len(bin(max(l)))-2

for i in range(n):
    l[i]=bin(l[i])[2:]

ll=[[0,0] for i in range(k)]
for i in range(n):
    for j in range(k):
        try:
            if l[i][-1-j]=="1":
                ll[j][1]+=1
            if l[i][-1-j]=="0":
                ll[j][0]+=1
        except IndexError:
            ll[j][0]+=1

m=0
for i in range(k):
    m+=ll[i][0]*ll[i][1]*(2**i)
print(m%(10**9+7))