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


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = {}
for i in range(m):
    b, c = map(int, input().split(' '))
    b_[c] = b_.get(c, 0)
    b_[c] += b
if max(b_.keys()) < min(a):
    print(result)
else:
    for j, k in enumerate(a):
        t = max(b_.keys())
        if k < t:
            a[j] = t
            b_[t] -= 1
        if b_[t] == 0:
            b_.pop(t)
        if b_ == {}:
            break
    print(sum(a))

### FIXED CODE ###


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    b_ += [(b,c)]
for i in range(n):
    b_ += [(1, a[i])]

from operator import itemgetter
b_.sort(key=itemgetter(1), reverse=True)

count = n
res = 0
for j, k in b_:
    if count > j:
        res += k * j
        count -= j
    elif count <= j:
        res += k * count
        break
print(res)
### BUGGY CODE ###

from functools import reduce
from operator import mul

MOD = 1000000007


def combination(n, r):
  r = min(n - r, r)
  if r == 0:
    return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1, r + 1))

  return over // under


def main():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD

  total = 0
  for x1 in range(M - 1):
    for x2 in range(x1 + 1, M):
      dx = x2 - x1
      # diff * n_x1 * n_x2 * combination
      total += (x2 - x1) * N * N * c
      total %= MOD

  for y1 in range(N - 1):
    for y2 in range(y1 + 1, N):
      total += (y2 - y1) * M * M * c
      total %= MOD

  print(total)


main()

### FIXED CODE ###

def mfactorial(n: int, mod: int) -> int:
  cache = mfactorial.__cache if hasattr(mfactorial, '__cache') else [1, 1]
  n_len = len(cache)
  n_new = n - n_len + 1
  if n_new > 0:
    cache = cache + ([0] * n_new)
    for i in range(n_len, n + 1):
      cache[i] = cache[i - 1] * i % mod
    mfactorial.__cache = cache

  return mfactorial.__cache[n]


def cmb(n, r, mod):
  result = mfactorial(n, mod)
  result *= pow(mfactorial(r, mod), mod - 2, mod) % mod
  result %= mod
  result *= pow(mfactorial(n - r, mod), mod - 2, mod) % mod
  result %= mod

  return result


def main():
  MOD = 10 ** 9 + 7

  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = cmb(N * M - 2, K - 2, MOD)

  X = 0
  Y = 0
  for i in range(M):
    X += (M - i) * i
  for i in range(N):
    Y += (N - i) * i

  total = (X * (N ** 2) + Y * (M ** 2)) % MOD * c % MOD
  print(total)


main()
### BUGGY CODE ###

import collections


def main():
    s = collections.deque(int(c) for c in input())
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

    temp = 0
    s_pop = s.pop
    for i in range(len(s)):
        temp += s_pop() * 10 ** i
        rem[temp % 2019] += 1

    return sum(c * (c - 1) // 2 for c in rem)


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

# https://www.hamayanhamayan.com/entry/2020/04/26/232032
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

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

def E(n):
  return sum(range(1,n+1)) / n

j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
  
else:
  flag = False
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]
          flag = True
  if flag:
    l2 = list(map(E, t))
  else:
    l2 = list(map(E, l))

  print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))
### BUGGY CODE ###

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

Asum=0
for i in range(N):
  for j in range(i):
    Asum+=(A[i]*A[j])%(10**9+7)
    Asum%=10**9+7

print(Asum)

### FIXED CODE ###

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

AjtoN=sum(A)
Asum=0
for i in range(N):
    AjtoN-=A[i]
    Asum+=A[i]*AjtoN
    Asum=Asum%(10**9+7)

print(Asum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(float, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
P = li()

dp = dp2(0, N+1, N)
dp[0][0] = 1 - P[0]
dp[0][1] = P[0]

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

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






### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(float, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
P = li()

dp = dp2(0, N+1, N)
dp[0][0] = 1 - P[0]
dp[0][1] = P[0]

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

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

# -*- coding: utf-8 -*-
from collections import deque
n = int(input())
a = [0 for _ in range(n)]
for i in range(n):
    a[i] = int(input())


colors = deque()
colors.append(a[0])
for num in a[1:]:
    exchange = False
    for i in range(len(colors)):
        if num > colors[i]:
            colors[i] = num
            exchange = True
            break
    if not exchange:
        colors.append(num)
print(len(colors))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect

n = int(input())
a = [0 for _ in range(n)]
for i in range(n):
    a[i] = -int(input())


LIS = list()
for i in a:
    j = bisect.bisect_right(LIS, i)
    if len(LIS) == j:
        LIS.append(i)
    else:
        LIS[j] = i

print(len(LIS))
### BUGGY CODE ###

#!/usr/bin/env python3

from itertools import product


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]
    labels = [i for i in range(n)]
    groups = {}
    for i in range(n):
        groups[i] = {i}


    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        if labels[ai] != labels[bi]:
            next_val = result[-1]
            label_a = labels[ai]
            label_b = labels[bi]
            next_val -= len(groups[label_a]) * len(groups[label_b])
            result.append(next_val)
            groups[label_a] |= groups[label_b]
            for bx in groups[label_b]:
                labels[bx] = labels[ai]
            del groups[label_b]
        else:
            result.append(result[-1])

    result.reverse()
    for v in result[1:]:
        print(v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from itertools import product
import sys
sys.setrecursionlimit(100000)

def get_label(labels, target):
    if labels[target] == -1:
        return target
    else:
        temp = get_label(labels, labels[target])
        labels[target] = temp
        return temp


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]
    labels = [-1] * n
    groups = {}
    for i in range(n):
        groups[i] = 1

    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        label_a = get_label(labels, ai)
        label_b = get_label(labels, bi)
        if label_a != label_b:
            next_val = result[-1]
            next_val -= groups[label_a] * groups[label_b]
            result.append(next_val)
            groups[label_a] += groups[label_b]
            labels[label_b] = label_a
            del groups[label_b]
        else:
            result.append(result[-1])

    result.reverse()
    for v in result[1:]:
        print(v)

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

sn = int(input())
S = [0 for i in range(sn)]
S = input().split()
for i in range(sn):
	S[i] = int(S[i])

tn = int(input())
T = [0 for i in range(tn)]
T = input().split()
for i in range(tn):
	T[i] = int(T[i])

A=[]
cnt=0

for i in range(tn):

	key=T[i]
	left=0
	right=sn

	while left<right:

		mid=(int)((left+right)/2)

		if S[mid]==key:
			if T[i] not in A:
				cnt+=1
			A.append(key)
			break

		if S[mid]>key:
			right=mid
			
		if S[mid]<key:
			left=mid+1


print(cnt)


### FIXED CODE ###


sn = int(input())
S = [0 for i in range(sn)]
S = input().split()
for i in range(sn):
	S[i] = int(S[i])

tn = int(input())
T = [0 for i in range(tn)]
T = input().split()
for i in range(tn):
	T[i] = int(T[i])


cnt=0

for i in range(tn):

	key=T[i]
	left=0
	right=sn
	c=0

	while left<right:

		mid=(int)((left+right)/2)

		if S[mid]==key:
			if c==0:
				cnt+=1
				c=1
				
			break

		if S[mid]>key:
			right=mid

		if S[mid]<key:
			left=mid+1


print(cnt)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 30
ans = 0
from bisect import bisect_left as bl, bisect_right as br
def sub(k):
    tmp = pow(2, k)
    bb = [item%(tmp*2) for item in b]
    bb.sort()
    ans = 0
    for item in a:
        aa = item%(tmp*2)
        if aa<=tmp:
            num = br(bb, tmp*2-1-aa) - bl(bb, tmp-aa)
        else:
            num = br(bb, tmp*2-1-aa) + (n - bl(bb, tmp*3-aa))
        ans += num
        ans %= 2
    return ans%2
    
for k in range(l):
    # i桁目を求める
    if sub(k):
        ans += pow(2, k)
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
 if s[i]=='?': #?のときは各値(0～9)について更新する
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): #整数のときはその値について更新する
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答

### FIXED CODE ###

'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
 if s[i]=='?': #?のときは各値(0～9)について更新する
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): #整数のときはその値について更新する
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答
### BUGGY CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 15

count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count = count + 1
                break
print(count)


### FIXED CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 14

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z <= k and 0 <= z:
            count += 1
print(count)
### BUGGY CODE ###

from collections import Counter
S = input()[::-1]
N = len(S)
l = [0]*N
for i in range(N):
    l[i] = (l[i-1]+int(S[i])*(10**i))%2019
c = Counter(l)
c[0] += 1
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
S = input()[::-1]
N = len(S)
l = [0]*N
for i in range(N):
    l[i] = (l[i-1]+int(S[i])*pow(10,i,2019))%2019
c = Counter(l)
c[0] += 1
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,S = inputIL()
l = inputIL()

dp = [[[0,0] for s in range(4000)] for r in range(4000)]

for r in range(N):
  for s in range(S):
    if s == 0:
      dp[r][s] = [1,r+2]
    if r == 0:
      if s == l[r]:
        dp[r][s] = [1,1]
      else:
        dp[r][s] = [0,0]
    else:
      dp[r][s] = [dp[r-1][s][0] + dp[r-1][s][1] + dp[r-1][s-l[r]][1]%MOD,dp[r-1][s][1]+dp[r-1][s-l[r]][1]%MOD] 


print(dp[N-1][S][0])


### FIXED CODE ###

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

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

dp = [0] * (S+1)
ans = 0
mod = 998244353

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(S):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S]
    ans %= mod

    dp = ndp

    #print (dp)

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

from copy import copy

N = int(input())
C = []
for _ in range(N):
    C.append(int(input()))

def is_fin(C):
    hist = set([C[0]])
    active = C[0]
    for i in C:
        if i != active:
            if i in hist:
                return False
            hist.add(i)
            active = i
    return True

ret = set()
def dfs(C, depth):
    if depth >=5 :
        return
    ret.add(str(C))
    if is_fin(C):
        return

    for i in range(len(C)):
        for j in range(i + 1, len(C)):
            if C[i] == C[j] and len(set(C[i:j])) >= 2:
                _C = copy(C)
                _C[i:j] = [C[i]] * (j - i)
                dfs(_C, depth+1)

dfs(C, 0)
print(len(ret))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
c = []
for _ in range(N):
    c.append(int(input()))

dp = [0] * N
dp[0] = 1
dpc = [0] * (max(c) + 1)
dpc[c[0]] = 1

for i in range(1, N):
    dp[i] = dp[i - 1]
    if c[i] != c[i - 1]:
        dp[i] += dpc[c[i]]
        dpc[c[i]] += dp[i - 1]

print(dp[N - 1] % (10**9+7))
### BUGGY CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                count+=1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z>=0 and z<=k:
            count+=1
print(count)
### BUGGY CODE ###


import math
import bisect


prime = [2,3,5,7,11,13,17,19]
for i in range(prime[-1]+2,100000,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
                
    if not found:
        prime.append(i)

# print(prime)


q = int(input())

for _ in range(q):

    l, r = map(int,input().split())
    l += 1 if l%2 == 0 else 0

#    print((l,r))

    ans = 0
    for i in range( l , r+1, 2):

        #si = bisect.bisect_left(prime,i)
        xi = bisect.bisect_right(prime, i)
        yi = bisect.bisect_right(prime, (i+1)//2)
        ans += 1 if prime[xi-1] == i and prime[yi-1] == (i+1)//2 else 0

    print(ans)

### FIXED CODE ###


import math
import bisect


prime = [2]

tab = [False]*100001
tab[2] = True
for i in range(3,100000+1,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)
        tab[i] = True

#print(prime[0:10])
#print(tab[0:10])
q = int(input())

ac = [0] * len(tab)

for i in range(1,len(ac)):
    ac[i] = ac[i-1] + (1 if tab[i] and tab[(i+1)//2] else 0)

#print(ac)
for _ in range(q):

    l, r = map(int,input().split())
    
    ans = ac[r] - ac[l-1]

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

import itertools
N = int(input())
S = input()
C = list(itertools.combinations(range(1, N + 1), 3))
count = 0
for i, j, k in C:
    if (i != 2 * j - k) and (S[i - 1] != S[j - 1] and S[i - 1] != S[k - 1] and S[j - 1] != S[k - 1]):
        count += 1
print(count)


### FIXED CODE ###

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


for j in range(N):
    for i in range(j):
        k = 2 * j - i
        if k >= N:
            continue
        if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]):
            count -= 1
print(count)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
print(sum((f//a)%mod for a in l )%mod)


### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc141/abc141_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    A = i2nn()
    A2 = sorted(A, reverse=True)
    for _ in range(M):
        discount(A2, N)
    print(sum(A2))
    return

def discount(A, N):
    A[0] = A[0] >> 1
    for i in range(N - 1):
        if A[i] < A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
        else:
            break
    # print(A)

main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc141/abc141_d
import sys
import heapq

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    h = [-int(s) for s in sys.stdin.readline().rstrip().split()]
    heapq.heapify(h)
    for _ in range(M):
        top_h = -(-h[0] // 2)
        heapq.heapreplace(h, top_h)
    print(-sum(h))

main()
### BUGGY CODE ###

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


listp = [[0 for j in range(31)] for i in range(N)] 
li = [0]*31
for i in range(N):
    for j in range(30,-1,-1):
        if A[i] >= 2**j:
            listp[i][j] = 1
            A[i] -= 2**j
            li[j] = li[j]+1
            if li[j] > 2:
                li[j] %= 2
for i in range(N):
    ans = 0
    for j in range(31):
        if li[j] - listp[i][j] %2 == 1:
            ans += 2**j
    print(ans, end=" ")

### FIXED CODE ###

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

s = 0
for i in range(N):
    s ^= A[i]
for i in range(N):
    ans = s^A[i]
    print(ans, end=" ")