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

N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][j+A[i]]%=mod
print(dp[N][S])


### FIXED CODE ###

N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][j+A[i]]%=mod
print(dp[N][S])
### BUGGY CODE ###

a,b=map(int,input().split(" "))
h="IMPOSSIBLE"
c=[a,b]
for i in range(len(str(min(c))),10**9):
    if abs(a-i)==abs(b-i):
        h=i
        break
print(h)


### FIXED CODE ###

a,b=map(int,input().split(" "))
if (a%2==0 and b%2==1) or (a%2==1 and b%2==0):
    print("IMPOSSIBLE") 
else:
    print(int((a+b)/2))
### BUGGY CODE ###

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

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]
        
    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))





### FIXED CODE ###

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

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = Puzzle()
                v[:] = u[:]
                v.path = u.path
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))
### BUGGY CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
A = [int(i) for i in input().split()]
k = [lcm_list(A)] * n
r = 0
for i in range(n):
    r += k[i]//A[i]
    if r > 10**9+7:
        r %= 10**9+7
print(r)

### FIXED CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [list(map(int, input().split())) for _ in range(Q)]

A_counter = Counter(A)
for b in B:
    cnt = A_counter[b[0]]
    A_counter[b[1]] += cnt
    del A_counter[b[0]]
    print(sum([num * cnt for num, cnt in A_counter.items()]))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [list(map(int, input().split())) for _ in range(Q)]

res = sum(A)
A_counter = Counter(A)
for i, j in B:
    if i not in A_counter:
        A_counter[i] = 0
    if j not in A_counter:
        A_counter[j] = 0

    res += (j - i) * A_counter[i]
    print(res)
    
    A_counter[j] += A_counter[i]
    A_counter[i] = 0
### BUGGY CODE ###

#
import sys

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
import time

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    start = time.time()

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        elapsed_time = time.time() - start
        if elapsed_time > 1.5:
            print(n * (n-1)//2)
            return

        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


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

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

def main():
    N, M, P = map(int, input().split())
    edge = []
    g = [[] for _ in range(N)]
    rg = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge.append((A,B,C))
        g[A].append(B)
        rg[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    visited = [False] * N
    rvisited = [False] * N
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        visited[v] = True
        for i in g[v]:
            if not visited[i]:
                Q.append(i)

    Q.append(N-1)
    while Q:
        v = Q.popleft()
        rvisited[v] = True
        for i in rg[v]:
            if not rvisited[i]:
                Q.append(i)
    
    OK = [False] * N
    for i in range(N):
        OK[i] = visited[i] & rvisited[i]
    
    flag = True
    d = [10 ** 9] * N
    d[0] = 0
    step = 0
    while flag:
        flag = False
        for A, B, C in edge:
            if not OK[A]:
                continue
            if not OK[B]:
                continue
            newD = d[A] + C
            if newD < d[B]:
                d[B] = newD
                flag = True
        step += 1
        if step > N:
            print(-1)
            exit()

    print(max(0,-d[N-1]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

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


def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    redge = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        redge[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    
    visited1, visited2 = {0}, {N-1}
    
    stack = [0]
    while stack:
        v = stack.pop()
        for dest, _ in edge[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            stack.append(dest)
    
    stack = [N-1]
    while stack:
        v = stack.pop()
        for dest in redge[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            stack.append(dest)
    
    OK = visited1 & visited2
    
    new_edge = [[] for _ in range(N)]
    for s in range(N):
        for t, c in edge[s]:
            if t in OK:
                new_edge[s].append((t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    #ベルマンフォード法、N回実行してまだ更新されている場合は負の閉路が存在する
    for _ in range(N):
        flag = False
        for v, e in enumerate(new_edge):
            for t, c in e:
                if d[v] != float('inf') and d[v] + c < d[t]:
                    d[t] = d[v] + c
                    flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


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

from bisect import bisect_right
import numpy as np
def calculate(arr,sArr):

    for s in range(len(sArr)):
        arr = np.sort(arr, axis=0)

        k = bisect_right(arr,sArr[s][1])

        if k == 0:
            break

        if k >= sArr[s][0]:
            arr[:sArr[s][0]] = sArr[s][1]
        else:
            arr[:k] = sArr[s][1]

    return arr


S = input()

N = int(S.split(" ")[0])
M = int(S.split(" ")[1])

arr = [int(s) for s in input().split(" ")]
arr = np.array(arr)


arr2 = []
for i in range(M):
    tmp = [int(s) for s in input().split(" ")]
    arr2.append(tmp)

arr2 = sorted(arr2,key=lambda x:-x[1])
arr2 = np.array(arr2)


result = calculate(arr,arr2)

print(np.sum(result))


### FIXED CODE ###

# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]


N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    raw = []
    for ar in arr:
        raw.append([ar, 1])
    for br in brr:
        raw.append([br[1], br[0]])

    raw = sorted(raw,key=lambda x:-x[0])
    # print(raw)

    offset = 0
    sum = 0
    for ra in raw:
        if offset + ra[1] <= n:
            sum = sum + ra[1] * ra[0]
            offset = offset + ra[1]
        else:
            sum = sum + (n - offset) * ra[0]
            offset = n
            break
    print(sum)

calculate(N, M, ARR, BRR)
### BUGGY CODE ###

N , K = map(int, input().split())
flag = "F"
while 1:
    a = N
    N = abs(N - K)

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)

### FIXED CODE ###

import math

N , K = map(int, input().split())
flag = "F"
if N !=0:
    while 1:
        lenN = int (math.log10(N) + 1)
        lenK = int (math.log10(K) + 1)
        N = abs(N-K*(10**abs(lenN-lenK-1)))
        lenN = int (math.log10(N) + 1)
        if abs(lenN-lenK)<2:
            break



        
while 1:
    
    
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)
### BUGGY CODE ###

from itertools import combinations_with_replacement

N = int(input())

ans = [0 for _ in range(1,N+1)]

for v in combinations_with_replacement(range(1,(N//6)+1), 3):
    x,y,z = v
    count = 0
    if x == y == z:
        fn = 6 * x * x
        count = 1
    else:
        fn = x*x + y*y + z*z + x*y + y*z + z*x
        count = 3
    if N >= fn:
        ans[fn-1] += count

print(*ans, sep='\n')


### FIXED CODE ###

N = int(input())
ans = [0 for _ in range(1,10101)]

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n < N+1:
                ans[n-1] += 1

print(*ans[:N],sep='\n')
### 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()))

C.sort(reverse=True)
tmp = []
ans = []

for i in range(X):
	for j in range(Y):
		tmp.append(A[i]+B[j])
tmp.sort(reverse=True)

for i in range(min(X*Y, K)):
	for j in range(Z):
		ans.append(tmp[i]+C[j])

ans.sort(reverse=True)

for i in range(min(K, X*Y*Z)):
	print(ans[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()))

C.sort(reverse=True)
tmp = []
ans = []

for i in range(X):
	for j in range(Y):
		tmp.append(A[i]+B[j])

tmp.sort(reverse=True)
del tmp[min(K, X*Y):]

for i in range(len(tmp)):
	for j in range(min(Z, K)):
		ans.append(tmp[i]+C[j])

ans.sort(reverse=True)

for i in range(min(K, X*Y*Z)):
	print(ans[i])
### BUGGY CODE ###

def find_gcd(x, y, gcd_dict):
    if (x, y) in gcd_dict.keys():
        return gcd_dict[x, y]
    elif (y, x) in gcd_dict.keys():
        return gcd_dict[y, x]
    else:
        x_first = x
        y_first = y
        gcd_dict[x, y] = x
        while(y): 
            x, y = y, x % y 

        #print(x_first, y_first)
        gcd_dict[x_first, y_first] = x

    return x

nums = int(input())
result = 0

gcd_dict = {}

for i in  range(1, nums+1):
    for j in range(1, nums+1):
        for l in range(1, nums+1):
            gcd = find_gcd(i, j, gcd_dict)
            result += find_gcd(gcd, l, gcd_dict)

print(result)

### FIXED CODE ###

from math import gcd

nums = int(input())
result = 0

gcd_dict = {}

for i in  range(1, nums+1):
    for j in range(1, nums+1):
        for l in range(1, nums+1):
            result += gcd(gcd(i, j), l)

print(result)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
#高さ。0~n-1でアクセス

#足場Nにたどり着くまでの最小コストを格納。アクセスは[N-1]
dp = [-1] * n

dp[0] = 0
dp[1] = abs(h[0] - h[1])

inf = float("inf") #毎回関数を呼び出さないように
import sys
sys.setrecursionlimit(10000000)
#足場x（0～n-1）にたどり着くまでの最小コストを返す関数。
def getdp(x):
    global dp
    global inf
    if dp[x] != -1: return dp[x] #0の場合と、既に求めた場合は値を返す

    #今度はここをfor文にする
    #飛ぶ距離は、1～ min（ジャンプ力, xと0の距離(=x))
    mindp = inf #最小値を初期化
    for i in range(1, min(k, x)+1, 1): #iはジャンプする距離(1~min(k,x))
        nowdp = getdp(x-i) + abs(h[x]-h[x-i])
        mindp = min(mindp, nowdp)
        dp[x] = mindp
    return(dp[x])

print(getdp(n-1))


### FIXED CODE ###

def solve():
  n,k=[int(i) for i in input().split()]
  h=[int(i) for i in input().split()]
  dp=[0]*n
  for i, hi in enumerate(h):
    if i==0: continue
    dp[i]=min([dp[j] + abs(hi-h[j]) for j in range(max(i-k,0),i)])
  return dp[n-1]
print(solve())
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n):
  a = 1
  for j in range(i + 1):
    if p[i] <= p[j]:
      next
    else:
      a = 0
      break
  ans += a
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1
pmin = p[0]
for i in range(1, n):
  if pmin >= p[i]:
    ans += 1
    pmin = p[i]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
sum = 0
for i in range(N):
  diff = i + A[i]
  for j in range(i+1, N):
    if (j - A[j]) == diff:
      sum += 1
print(sum)

### FIXED CODE ###

from collections import defaultdict
 
N = int(input())	# 使わない
 
# j - i = A[i] + A[j] から、
# i + A[i] = j - A[j] となり、iとjが独立するため、同時並行で処理
L = defaultdict(lambda: 0)
R = defaultdict(lambda: 0)
for i, val in enumerate(map(int, input().split())):
  L[i - val] += 1	# i - val <= j - A[j]
  R[i + val] += 1	# i + val <= i + A[i]
  
cnt = 0
for key, val in L.items():
  if key > 0:
    cnt += L[key] * R[key]
    
print(cnt)
### BUGGY CODE ###

s = list(input().strip())
n = len(s)
end = n - 2

count = 0

if n >= 3:
  i = 0
  while i < end:
    if s[i] == 'A' and s[i + 1] == 'B' and s[i + 2] == 'C':
      s[i] = 'B'
      s[i + 1] = 'C'
      s[i + 2] = 'A'
      count = count + 1

      j = i - 1
      while j >= 0:
        if s[j] == 'A':
          s[j] = 'B'
          s[j + 1] = 'C'
          s[j + 2] = 'A'
          j = j - 1
          count = count + 1
        else:
          break

      i = i + 2
    else:
      i = i + 1

print(count)

### FIXED CODE ###

s = input().strip().replace('BC', 'D')
n = len(s)

count = 0
a_count = 0
for i in range(n):
  if s[i] == 'A':
    a_count += 1
  elif a_count > 0 and s[i] == 'D':
    count += a_count
  else:
    a_count = 0

print(count)
### BUGGY CODE ###

s = input()
K = int(input())

substrings = set()
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        substrings.add(s[i:j])

print(sorted(substrings)[K-1])
        


### FIXED CODE ###

s = input()
K = int(input())

substrings = set()
for i in range(len(s)):
    for j in range(i+1,min(i+6,len(s)+1)):
        substrings.add(s[i:j])

print(sorted(substrings)[K-1])
### BUGGY CODE ###

from math import sqrt
from fractions import gcd
from collections import defaultdict
from copy import deepcopy

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

def f(n):
    d = defaultdict(int)
    if n % 2 == 0:
        r = 0
        while n % 2 == 0:
            n //= 2
            r += 1
        d[2] = r
    for i in range(3,int(sqrt(n))+1):
        if n % i == 0:
            s = 0
            while n % i == 0:
                n //= i
                s += 1
            d[i] = s
    if n != 1:
        d[n] = 1
    return d

B = []
for i in range(N):
    B.append(f(A[i]))

lp = deepcopy(B[0])

for i in range(N-1):
    for j in list(set(B[i+1].keys()) | set(lp.keys())):
        lp[j] = max(B[i+1][j],lp[j])

ans = 0

for i in range(N):
    r = 1
    for j in list(lp.keys()):
        r = (r*pow(j,lp[j]-B[i][j],mod)) % mod
    ans = (ans + r) % mod

print(ans)


### FIXED CODE ###

def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

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

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

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

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    # 全ルートの中で、連続する#の数が一番少ないものを探す

    ans = [H+W]
    dir = ((1, 0), (0, 1))
    # 前の色、前の進行方向、今までの連続ブロックの数
    
    def dfs(x, y, pw, pd, cnt):
        if x==W-1 and y==H-1:
            if pw=='.' and s[y][x]=='#':
                cnt += 1
            ans[0] = min(cnt, ans[0])
        else:
            for d in dir:
                nx = x+d[0]
                ny = y+d[1]
                if nx<W and ny<H:
                    ncnt = cnt
                    # 前が白で今が黒
                    if pw=='.' and s[y][x]=='#':
                        ncnt += 1
                    dfs(nx, ny, s[y][x], d, ncnt)

    dfs(0, 0, '.', dir[0], 0)
    print(ans[0])

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    ans = [[0]*W for _ in range(H)]
    if s[0][0]=='#':
        ans[0][0] = 1
    for i in range(1, W+H-1):
        for y in range(max(0, i-(W-1)), min(i+1, H)):
            x = i-y
            if y==0:
                if s[y][x-1]=='.' and s[y][x]=='#':
                    ans[y][x] = ans[y][x-1] + 1
                else:
                    ans[y][x] = ans[y][x-1]
            elif x==0:
                if s[y-1][x]=='.' and s[y][x]=='#':
                    ans[y][x] = ans[y-1][x] + 1
                else:
                    ans[y][x] = ans[y-1][x]
            else:
                if s[y][x]=='#':
                    ans[y][x] = min(ans[y-1][x]+(1 if s[y-1][x]=='.' else 0), ans[y][x-1]+(1 if s[y][x-1]=='.' else 0))
                else:
                    ans[y][x] = min(ans[y-1][x], ans[y][x-1])
    print(ans[-1][-1])

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

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

for i in range(m):
  a[a.index(max(a))]=int((max(a)/2)//1)
     
print(sum(a))


### FIXED CODE ###

import heapq as hq
n,m=map(int,input().split())
a=[-int(x) for x in input().split()]
hq.heapify(a)
for i in range(m):
    x=hq.heappop(a)
    x=-x//2
    hq.heappush(a,-x)
 
print(sum(a)*-1)