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

n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=dp_1[i-1][j]+dp_1[i-1][j-a_list[i]]
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=Sum+dp[n][i]*3
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)



### FIXED CODE ###

n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=(dp_1[i-1][j]+dp_1[i-1][j-a_list[i]])%mod
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]%mod
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=(Sum+dp[n][i]*3)%mod
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)
### BUGGY CODE ###

s = input()
slen = len(s)
ans = 0

while(1):
  sub = s
  s = s.replace("01",'').strip()
  s = s.replace("10",'').strip()
  if sub == s:
    break
  

print(slen-len(s))



### FIXED CODE ###

s = input()
print(2*min(s.count("0"),s.count("1")))
### BUGGY CODE ###

s=input()
n=len(s)
count=0
if n<4:
    print(0)
else:
    for i in reversed(range(2,n)):
        k=int(s[i-2:i+1])
        h=3
        for j in reversed(range(0,i-2)):
            k=k+(10**(h)%2019)*int(s[j])
            h+=1
            if k%2019==0:
                count+=1
    print(count)

### FIXED CODE ###

import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
b=[0 for i in range(n)]
b[0]=1
for i in range(1,n):
    b[i]=b[i-1]*10%2019
for i in reversed(range(0,n)):
    k+=(b[n-i-1])*int(s[i])%2019
    a[k%2019]+=1        
for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

n = int(input())

s = input()

sum_list = []

for i in range(n):
    if i == 0:
        sum_list.append(s[i + 1:].count('E'))
    elif i == n - 1:
        sum_list.append(s[:i].count('W'))
    else:
        sum_list.append(s[:i].count('W') + s[i + 1:].count('E'))

print(min(sum_list))

### FIXED CODE ###

N=int(input())
S=input()

current_and_left_w=0
ans=current_and_right_e=S.count("E")

for i in S:
    if i=="E":
        current_and_right_e-=1
    else: 
        current_and_left_w+=1
        
    ans=min(ans,current_and_right_e+current_and_left_w)
print(ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
for i in range(q):
    i,j = map(int, input().split())
    print(s[i-1:j].count("AC"))

### FIXED CODE ###

def get_ac_count(S):
    buf = None
    temp = []
    count = 0
    for c in S:
        if c == "A":
            buf = "A"
        elif buf == "A" and c == "C":
            buf = None
            count += 1
        elif buf == "A":
            buf = None
        temp.append(count)
    return temp
N, Q = map(int, input().split())
S = input()
ac_count = get_ac_count(S)
for i in range(Q):
    l,r = map(int, input().split())
    print(ac_count[r-1]-ac_count[l-1])
### BUGGY CODE ###

def main():
    n, k, *a = map(int, open(0).read().split())
    s = set(a)
    v = len(s) - k
    l = sorted([a.count(i) for i in s])
    ans = sum(l[:v])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter

    n, k, *a = map(int, open(0).read().split())
    c = Counter(a)
    v = len(c)
    l = list(c.values())
    l.sort()
    ans = sum(l[:v - k])
    print(ans)


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

N=int(input())
S=input()
R=[]
G=[]
B=[]
for n in range(N):
    if S[n]=="R":
        R.append(n)
    elif S[n]=="G":
        G.append(n)
    else:
        B.append(n)

x=0
for r in R:
    for g in G:
        for b in B:
            l=[r,g,b]
            if sum(l)/3 in l:
                pass
            else:
                x+=1

print(x)

### FIXED CODE ###

N=int(input())
S=input()
R=[]
G=[]
B=[]

for n in range(N):
    if S[n]=="R":
        R.append(n)
    elif S[n]=="G":
        G.append(n)
    else:
        B.append(n)

ANS=len(R)*len(G)*len(B)

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


print(ANS)
### BUGGY CODE ###

# -*- coding: UTF-8 -*-

n = int(input())
l = []

for i in range(n):
    a = list(str(input()))
    a.sort()
    l.append("".join(a))

p = 0

for i in range(n):
    for j in range(n - i - 1):
        if l[i] == l[i+j+1]:
            p += 1

print(p)


### FIXED CODE ###

# -*- coding: UTF-8 -*-

n = int(input())
l = []

for i in range(n):
    l.append("".join(sorted(str(input()))))

l.sort()

p = 0
s = 1
f = 0

for i in range(n-1):
    if l[i] == l[i+1] and i != n-2:
        s += 1
        f = 1

    elif l[i] != l[i+1] and f == 1:
        f = 0
        p += int(s * (s-1) / 2)
        s = 1

    elif l[i] == l[i+1] and i == n-2:
        s += 1
        f = 0
        p += int(s * (s-1) / 2)


print(p)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
cnt=0
for j in range(m):
  for k in range(m):
    if j==k:
      continue;
    else:
      a=set(lst[j])|set(lst[k])
      if len(a)==3 and 1 in a and n in a:
        cnt+=1
if cnt>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")


### FIXED CODE ###

n,m=map(int,input().split())
c=set()
d=set()
for i in range(m):
  a,b=map(int,input().split())
  if a==1 or a==n:
    c.add(b)
  elif b==1 or b==n:
    d.add(a)
if len(c&d)==1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
B = []
for i in range(N):
    if A[i] != 0:
        B.append(A[i])
N = len(B)
P = 200003

d = {}
D = []
a = 1
for i in range(P-1):
    D.append(a)
    d[a] = i
    a *= 2
    a %= P

E = [0]*(P-1)
for i in range(P-1):
    if D[i]*2 > P:
        E[i] = 1

C = []
for i in range(N):
    C.append(d[B[i]])

c = len(C)
ANS = [0]*(P-1)
for i in range(c-1):
    for j in range(i+1,c):
        ANS[(C[i]+C[j]) % (P-1)] += 1

x = sum(D[i]*ANS[i] for i in range(P-1))
print(x)
# a = sum(B)
# b = sum(B[i]**2 for i in range(N))
# r = ((a**2-b)//2) % P

# print(P*x+r,C)

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()
B = []
for i in range(N):
    if A[i] != 0:
        B.append(A[i])
N = len(B)
P = 200003

# 2はPの原始根

C = []  # C[i] = (2**i mod P)
d = {}  # d[n] = (2**i == n たるi)
a = 1
for i in range(P-1):
    C.append(a)
    d[a] = i
    a *= 2
    a %= P

D = [0]*(P-1)
for i in range(N):
    D[d[B[i]]] += 1

n = 2**((2*P-3).bit_length())
D += [0]*(n-(P-1))


from cmath import pi,exp

def dfs(f,start,step,N,inverse=False):
    if N == 2:
        a,b = f[start],f[start+step]
        return [a+b,a-b]
    if inverse is False:
        f0 = dfs(f,start,2*step,N//2,inverse=False)
        f1 = dfs(f,start+step,2*step,N//2,inverse=False)
        z = exp(2j*pi/N)
    else:
        f0 = dfs(f,start,2*step,N//2,inverse=True)
        f1 = dfs(f,start+step,2*step,N//2,inverse=True)
        z = exp(-2j*pi/N)
    z0 = 1.0
    for i in range(N//2):
        a,b = f0[i],f1[i]*z0
        f0[i],f1[i] = a+b,a-b
        z0 *= z
    return f0+f1

def DFT(f,N):  # fを離散フーリエ変換
    if N == 1:
        return f
    return dfs(f,0,1,N)

def iDFT(F,N):  # Fを離散フーリエ逆変換
    if N == 1:
        return F
    f = dfs(F,0,1,N,inverse=True)
    for i in range(N):
        f[i] /= N
    return f

# deg(f)+deg(g)<Nとなる2冪Nを選び、f,gの長さがNになるように0を埋めておく

def product(f,g,N):  # 多項式f,gの積
    F = DFT(f,N)
    G = DFT(g,N)
    FG = [F[i]*G[i] for i in range(N)]
    fg = iDFT(FG,N)
    for i in range(N):
        fg[i] = int(fg[i].real+0.5)
    return fg


E = product(D,D,n)
ans = 0
for i in range(P-1):
    ans += (C[i]*(E[i]+E[i+(P-1)]))

for i in range(N):
    ans -= (B[i]**2) % P

print(ans//2)
### BUGGY CODE ###

import numpy as np
K = (int)(input())
sum = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            sum += np.gcd(np.gcd(a,b),c)
print(sum)

### FIXED CODE ###

s = input()
a = 0
for i in range(len(s)):
    if (s[i] == '7'):
        print("Yes") 
        a = 1
        break
if(a == 0):
    print("No")
### BUGGY CODE ###

from heapq import heapify, merge, nlargest
from operator import itemgetter

n, m = map(int, input().split())
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
heapify(aa)
bcbc.sort(key=itemgetter(1), reverse=True)

for b, c in bcbc :
    cc = [c]*min(b, n)
    dd = merge(aa, cc)
    dd = nlargest(n, dd)
    if aa == dd :
        break
    aa = dd
print(sum(dd))

### FIXED CODE ###

from operator import itemgetter

n, m = map(int, input().split())
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
bcbc.extend([[1, a] for a in aa])
bcbc.sort(key=itemgetter(1), reverse=True)

count = 0
s = 0
for b, c in bcbc :
    if count + b >= n :
        b = n - count
    count += b
    s += b*c
    if count == n :
        break
print(s)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
X, Y = MAP()

# ランレングス圧縮
A1, A2 = [], []
cnt = d = 0
for s in S:
    if s == 'T':
        if d == 0:
            A1.append(cnt)
        else:
            A2.append(cnt)
        cnt = 0
        d ^= 1
    else:
        cnt += 1
if d == 0:
    A1.append(cnt)
else:
    A2.append(cnt)
# 最初だけ右固定なので別処理
X -= A1[0]
A1.pop(0)

# 縦横独立に、到達可の場所を確認する
M1 = len(A1)
M2 = len(A2)
dpx = [set() for i in range(M1+1)]
dpy = [set() for i in range(M2+1)]
dpx[0].add(0)
dpy[0].add(0)
for i, a in enumerate(A1):
    for x in dpx[i]:
        dpx[i+1].add(x+a)
        dpx[i+1].add(x-a)
for i, a in enumerate(A2):
    for y in dpy[i]:
        dpy[i+1].add(y+a)
        dpy[i+1].add(y-a)

if X in dpx[M1] and Y in dpy[M2]:
    Yes()
else:
    No()


### FIXED CODE ###

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

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・メモリ節約のため、dictをsetにした。
・さらに使い終わった1つ前はもういらないので消すことにした。
"""

S = input()
X, Y = map(int, input().split())

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# あるかないか分かればいいので、dictじゃなくてsetにする
dpx = [set() for _ in range(len(S2))]
dpy = [set() for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0].add(S2[0])
dpx[1].add(S2[0])
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[0].add(0)
dpy[1].add(S2[1])
dpy[1].add(-S2[1])
for i in range(2, len(S2)):
    # 左右に移動する
    for v in dpx[i-1]:
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i].add(v-S2[i])
            dpx[i].add(v+S2[i])
        else:
            # yをやる時はxはそのまま
            dpx[i].add(v)
    # 1つ前は使い終わったので削除
    dpx[i-1] = set()
    # 上下に移動する
    for v in dpy[i-1]:
        if i % 2 == 1:
            dpy[i].add(v-S2[i])
            dpy[i].add(v+S2[i])
        else:
            dpy[i].add(v)
    dpy[i-1] = set()
# 最後のstepでXとYが到達可能ならOK
if X in dpx[len(S2)-1] and Y in dpy[len(S2)-1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.array = [0] * (n + 1)
        self.e = [0] * n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        self.e[i] += x
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


n, q = map(int, input().split())
*C, = map(lambda x: int(x) - 1, input().split())
P = [0] * n
N = [0] * n
for i in range(n)[::-1]:
    if P[C[i]]:
        N[i] = P[C[i]]
    P[C[i]] = i
F = [0] * n
B = BIT(n)
for i in range(n):
    if F[C[i]] == 0:
        B.add(i, 1)
        F[C[i]] = 1
XY = sorted([(tuple(map(int, input().split())), _) for _ in range(q)])
a = 0
lst = []
for (x, y), _ in XY:
    for i in range(a, x - 1):
        B.add(N[i], 1)
    a = x - 1
    lst.append((_, B.sum(y) - B.sum(x - 1)))
lst.sort()
for _, ans in lst:
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()
### BUGGY CODE ###

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

out = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                out += 1
print(out)


### FIXED CODE ###

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

out = 0

# 全探査だと間に合わない
# zはあるかないかの２択なので外せる
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0 <= z <= K:
            out += 1
print(out)
### BUGGY CODE ###

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

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(60):
    B = [(A[j]>>i)&1 for j in range(N)]
    c = B.count(0)
    ans += c*(N-c)*2**i%MOD

print(ans%MOD)

### FIXED CODE ###

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

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

for i in range(60):
    for j in range(N):
        if (A[j]>>i)&1 == 0:
            C[i] += 1
        else:
            B[i] += 1

ans = 0
for i in range(60):
    ans += B[i]*C[i]*2**i%MOD
print(ans%MOD)
### BUGGY CODE ###

import bisect
import sys

import numpy as np

sys.setrecursionlimit(200000)


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


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    # AB = iml(N)
    takahashi = {}
    aoki = {}
    for i in range(N):
        a = il()
        takahashi[i] = a[0]
        aoki[i] = a[1]
    T = [i[0] for i in sorted(takahashi.items(), key=lambda x: x[1])]
    A = [i[0] for i in sorted(aoki.items(), key=lambda x: x[1])]
    ind = [T.pop()]
    t = takahashi[ind[0]]
    a = 0
    for i in range(1, N):
        if i % 2 == 1:
            while A:
                j = A.pop()
                if j not in ind:
                    break
            a += aoki[j]
        else:
            while T:
                j = T.pop()
                if j not in ind:
                    break
            t += takahashi[j]
        ind.append(j)
    return t - a


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


### FIXED CODE ###

import sys

import numpy as np

sys.setrecursionlimit(200000)


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


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    AB = iml(N)
    ll = []
    for a, b in AB:
        ll.append(a + b)
    ind = np.argsort(ll)[::-1]
    t = [AB[i][0] for i in ind[::2]]
    a = [AB[i][1] for i in ind[1::2]]
    return sum(t) - sum(a)


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

H,N=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(N)]
from collections import deque

ans=[10**9]*(H+1)
ans[0]=0
que=deque([0])
while que:
    x=que.popleft()
    for a,b in ab:
        a=min(a,H-x)
        if ans[x+a]>ans[x]+b:
            ans[x+a]=ans[x]+b
            que.append(x+a)

print(ans[H])

### FIXED CODE ###

H,N=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(N)]
ab.sort()

ans=[10**9]*(H+1)
ans[0]=0
i=0
while i<=H:
    for a,b in ab:
        if a+i>H:
            a=H-i
        if ans[i+a]>ans[i]+b:
            ans[i+a]=ans[i]+b
    i+=1

print(ans[H])
### BUGGY CODE ###

#D
s = input()
count = 0
for left in range(len(s) - 3):
    for right in range(left + 3, len(s)):
        if int(s[left:right + 1]) % 2019 == 0:
            count += 1
print(count)


### FIXED CODE ###

s = input()
ans = 0
a = [0] * 2019
a[0] = 1
k = 0
mod = 1
for i in range(len(s) - 1, -1, -1):
    k = (k + int(s[i]) * mod) % 2019
    mod = (mod * 10) % 2019
    a[k] += 1
for i in a:
    ans += i * (i - 1) * 0.5
print(int(ans))
### BUGGY CODE ###

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

A.sort(reverse = True)

n = 0
if N > 1:
    while not M == 0:

        while A[0] >= A[1]:
            A[n] //= 2
            M -= 1
            if M == 0:
                break
        if M == 0:
            break

        a = A.pop(0)
        for i, num in enumerate(A):
            if num < a:
                A.insert(i, a)
                break
else:
    A[0] //= (2**M)


result = sum(A)
print(result)


### FIXED CODE ###

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

for i in range(len(A)):
    A[i] *= -1

import heapq

heapq.heapify(A)


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


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


A=[]
n=int(input())
for i in range(n):
    num=int(input())
    if(num in A):
        A.remove(num)
    else:
        A.append(num)
print(len(A))


### FIXED CODE ###

A={-1:False}
n=int(input())
count=0
for i in range(n):
    num=int(input())
    try:
        
        if(A[num]==True):
            count-=1
            A[num]=False
        else:
            count+=1
            A[num]=True
    except:
        #print("exception",A,num)
        A[num]=True
        count+=1
print(count)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
    if i<a+k:
        print(i)
    elif b-k<i:
        print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
if k*2>b:
    for i in range(a,b+1):
        if i<a+k:
            print(i)
        elif b-k<i:
            print(i)
else:
    for i in range(a,min(a+k,b+1)):
        print(i)
    for i in range(max(a+k,b-k+1),b+1):
        print(i)
### BUGGY CODE ###

N = int(input())
 
for n in range(1,N+1):
  ans = 0
  check = False
  for x in range(1,n):
    for y in range(x,n):
      for z in range(y,n):
        if (x**2 + y**2 + z**2 + x*y + y*z + z*x) == n:
          if x == y and y == x and z == x:
            ans += 1
          elif x == y  or z == x or y == z:
            ans += 3
          elif x != y and y != z and z != x:
            ans += 6
  print(ans)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10001)]

for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      v = i*i + j*j + k*k + i*j + j*k + k*i
      if v < 10001:
        ans[v] += 1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

N=int(input())
List = list(map(int, input().split()))
AList = []

i=1
while i<=N:
    AList.append((List.index(i))+1)
    i+=1
    
print(*AList)

### FIXED CODE ###

N=int(input())
List = list(map(int, input().split()))
AList = [0]*N
for i in range(0,N):
    S=List[i]
    AList[S-1]=i+1
    
print(*AList)
### BUGGY CODE ###

# 白色マスで４方向のマスに黒マスが一つ以上存在するものを黒にかえる。
# 何回の操作でマスが全て黒マスになるか？
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_list = []
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            black_list.append((h, w))

count = 0
move = ((0, 1), (1, 0), (-1, 0), (0, -1))
while black_list:
    n_pl = []
    for b in black_list:
        for m in move:
            n_p = (b[0] + m[0], b[1] + m[1])
            if not(n_p[0] < 0 or n_p[1] < 0 or n_p[0] >= H or n_p[1] >= W) and field[n_p[0]][n_p[1]] == ".":
                field[n_p[0]][n_p[1]] = "#"
                n_pl.append(n_p)
    black_list = n_pl
    count += 1
print(count-1)


### FIXED CODE ###

# 白色マスで４方向のマスに黒マスが一つ以上存在するものを黒にかえる。
# 何回の操作でマスが全て黒マスになるか？
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_list = []
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            black_list.append((h, w))

count = 0
move = ((0, 1), (1, 0), (-1, 0), (0, -1))
# 広がり方は一点の黒から一定なのでそれを行うことで、計算量を改善できる？
while black_list:
    n_pl = []
    for b in black_list:
        for m in move:
            n_p = (b[0] + m[0], b[1] + m[1])
            if not(n_p[0] < 0 or n_p[1] < 0 or n_p[0] >= H or n_p[1] >= W) and field[n_p[0]][n_p[1]] == ".":
                field[n_p[0]][n_p[1]] = "#"
                n_pl.append(n_p)
    black_list = n_pl
    count += 1
print(count-1)