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

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

INF = 1<<20

dp = [[INF] * 55 for i in range(1<<n)]
dp[0][0] = 0

for b in range(1<<n):
    # 使ったカードの枚数
    bitcnt = bin(b).count("1")
    cur = bitcnt 
    rest = [] 
    for i in range(n):
        # i番目のbitが立っているかの判定
        if not (b & (1 << i)):
            rest.append((i,cur))
            cur += 1
    # A,Bの制約から、sは55まででOK
    for s in range(51):
        if dp[b][s] >= INF:
            continue
        # 残ったカードで更新
        for i,cur in rest:
            if abs(bitcnt - i) % 2 == 0:
                num = As[i]
            else:
                num = Bs[i]
            if num >= s:
                d = abs(bitcnt - cur) 
                dp[b|(1<<i)][num] = min(dp[b|(1<<i)][num], dp[b][s] + d)
            

ans = min(dp[(1<<n)-1])
print(ans if ans != INF else -1)    
        
    


### FIXED CODE ###

from itertools import combinations
n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

even = []   #偶数番目で表になる
odd = []    #奇数番目で表になる
for i,(a,b) in enumerate(zip(As,Bs)):
    if i%2 == 0:
        even.append(a)
        odd.append(b)
    else:
        even.append(b)
        odd.append(a)



def check(n, even, odd):
    prev = -10**10
    ps = []
    for i in range(n):
        if i%2 == 0:
            if prev > even[i//2][0]:
                return False,-1
            else:
                ps.append(even[i//2][1])
            prev = even[i//2][0]
        else:
            if prev > odd[i//2][0]:
                return  False, -1
            else:
                ps.append(odd[i//2][1])
            prev = odd[i//2][0]
    return True, ps
    


def inversion(a):
    n = len(a)
    cnt = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                cnt +=1
    return cnt
 
#偶数としてpickupするやつ
INF = 10**10
ans = 10**10
for l in combinations(range(n), (n-1)//2+1):
    cnt = 0
    even_selected = [(even[i],i) for i in range(n) if i in l]
    odd_selected = [(odd[i],i) for i in range(n) if i not in l]
    # こいつらを昇順に並べられるか
    even_selected.sort()
    odd_selected.sort()
    is_possible, a = check(n, even_selected, odd_selected)
    # 並び順が正しければ
    if is_possible:
        cnt = inversion(a)
        ans = min(cnt, ans)
        
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split(' '))

S = [input() + '#' for _ in range(H)]
S.append('#' * (W + 1))

rows = np.zeros(shape=(H, W), dtype=np.int64)
cols = np.zeros(shape=(W, H), dtype=np.int64)

for y in range(H):
    cont = 0
    for x in range(W + 1):
        if S[y][x] == '.':
            cont += 1
        else:
            rows[y][x - cont:x] = cont
            cont = 0

for x in range(W):
    cont = 0
    for y in range(H + 1):
        if S[y][x] == '.':
            cont += 1
        else:
            cols[x][y - cont:y] = cont
            cont = 0

print(np.max(rows + cols.T) - 1)


### FIXED CODE ###

H, W = map(int, input().split(' '))

S = [input() for _ in range(H)]

rows = []
cols = []

for y in range(H):
    cont = 0
    row = []
    for x in range(W):
        if S[y][x] == '.':
            cont += 1
        else:
            for _ in range(cont):
                row.append(cont)
            row.append(0)
            cont = 0
    for _ in range(cont):
        row.append(cont)
    rows.append(row)

for x in range(W):
    cont = 0
    col = []
    for y in range(H):
        if S[y][x] == '.':
            cont += 1
        else:
            for _ in range(cont):
                col.append(cont)
            col.append(0)
            cont = 0
    for _ in range(cont):
        col.append(cont)
    cols.append(col)

ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '.':
            ans = max(ans, rows[y][x] + cols[x][y] - 1)

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

import itertools

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

res = list(itertools.combinations(A, 3))

ans = 0
for i in range(len(res)):
  if max(res[i])*2 < sum(res[i]):
    ans += 1
    
    
print(ans)

### FIXED CODE ###

import bisect

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

for i in range(N-1):
  k = A[i]
  for j in range(i+1, N):
    l = A[j]
    res = bisect.bisect_left(A, k+l)
    ans += res-j-1
    
print(ans)
### BUGGY CODE ###

#木の根を得る
def root(x):
    while par[x] >= 0:
        x = par[x]
    return x

#木の併合
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        if rx > ry:
            rx, ry = ry, rx
        par[rx] += par[ry]
        par[ry] = rx

from collections import defaultdict
T = defaultdict(int)
N, M = map(int, input().split())
par = [-1]*N
g = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A, B = A - 1, B - 1
    unite(A, B)
    g[A].append(B)
    g[B].append(A)

for i in range(N):
    T[root(i)] += 1

ans = 0
for k in T.values():
    ans = max(ans, k)
print(ans)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
K = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    K[A].append(B)
    K[B].append(A)
used = [0]*N
ans = 0
for i in range(N):
    c = 0
    if used[i] == 0:
        P = deque([i])
        used[i] = 1
        while P:
            c += 1
            a = P.popleft()
            for j in K[a]:
                if used[j] == 0:
                    used[j] = 1
                    P.append(j)
    ans = max(c, ans)
print(ans)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
abc= [list((map(int,input().split()))) for _ in range(3)]
from itertools import product as pro
ans = []
for a in pro(abc[0],abc[1],abc[2]):
    ans.append(int(a[0])+int(a[1])+int(a[2]))
ans.sort(reverse=1)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

*XYZ,K = map(int,input().split())
ABC = [list(map(int,input().split())) for i in range(3)]
for a in ABC:
    a.sort(reverse=1)
import heapq
ans = [0]*K
for a in ABC[0]:
    for b in ABC[1]:
        for c in ABC[2]:
            if a+b+c>ans[0]:
                heapq.heappush(ans,a+b+c)
                heapq.heappop(ans)
            else:
                break
ans.sort(reverse=1)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = {}
    for _ in range(M):
        (A,B) = map(int, input().split())
        na = neighbor.get(A, [])
        nb = neighbor.get(B, [])
        neighbor.update({A:(na+[B])})
        neighbor.update({B:(nb+[A])})

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor.get(n, [])
        # すでに道しるべがあるものは除く
        dests = list(filter(lambda d: not d in guide.keys(), dests))
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            # 探索候補の末尾に追加
            target += d,

    if set(range(1,N+1)) <= set(guide.keys()):
        print('Yes')
        for i in range(2,N+1):
            print(guide[i])
    else:
        print('No')

main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

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

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: guide[d] == 0, dests)
        # 道しるべを置く
        for d in dests:
            guide[d] = n
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    print('Yes')
    for i in range(2,N+1):
        print(guide[i])

main()
### BUGGY CODE ###

import numpy as np

N = int(input())
Ps = list(map(int, input().split()))
Ps = np.array(Ps)
count = 0
low = -1

for i in range(N):
    low = Ps[i]

    if ( np.any(Ps[:i] < low) ):
        continue
    else :
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
Ps = list(map(int, input().split()))
count = 0
min = Ps[0]+1

for i in range(N):
    if (Ps[i] < min):
        min = Ps[i]
        count += 1

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

R,G,B,N=(int(x) for x in input().split())
conbo=[]
max=[N//R,N//G,N//B]
for r in range(max[0]+1):
    for g in range(max[1]+1):
        for b in range(max[2]+1):
            v=(R*r)+(G*g)+(B*b)
            if v>N:
                continue
            if v==N:
                conbo.append([r,g,b])
print (len(conbo))

### FIXED CODE ###

R,G,B,N=list(map(int,input().split()))
cnt=0
for r in range((N//R)+1):
    for g in range(((N-R*r)//G)+1):
        if (N-R*r-G*g)%B==0:
            cnt=cnt+1
print (cnt)
### BUGGY CODE ###

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

for i in range(N):
    X = sorted(x[:i] + x[i+1:])
    print(X[(N-1)//2])


### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
sx = sorted(x)
a = sx[N//2-1]
b = sx[N//2]

for c in x:
    if c <= a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

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

value_and_index = []
for i in list:
    value_and_index.append([i,list.index(i)+1])
value_and_index.sort()

for i in value_and_index:
    print(i[1], end = " ")

### FIXED CODE ###

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

dict = {}
count = 1

for i in list:
    dict[i]= count
    count += 1
for i in range(1, n+1):
    print(dict[i], end = " ")
### BUGGY CODE ###

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

S = []
max_num = 0
for i in range(N):
    if i+K <= N:
        tmp = sum(P[i:i+K])
        if tmp  > max_num:
            max_num = tmp
            S = P[i:i+K]
    else:
        break

ans = 0
for i in range(len(S)):
    gausu = (S[i])*(S[i]+1)/2
    ans += (gausu/S[i])

print(ans)

### FIXED CODE ###

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

S = [0]
before = 0
for i in range(N):
    S.append(P[i]+before)
    before += P[i]

max_num = 0
l = 0
m = 0
for i in range(N):
    if K+i > N:
        break
    tmp = S[K+i]-S[i]
    if tmp > max_num :
        l = K+i
        m = i
        max_num = tmp

S = P[m:l]
ans = 0
for i in range(len(S)):
    gausu = (S[i])*(S[i]+1)/2
    ans += (gausu/S[i])

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

import fractions
from functools import reduce
from copy import copy


def main():
    N = int(input())
    A = list(map(int, input().split()))
    gcds = []
    for i in range(N):
        A_ = copy(A)
        A_.pop(i)
        gcds.append(gcd(*A_))
    print(max(gcds))


def gcd(*nums):
    return reduce(fractions.gcd, nums)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd


def main():
    N = int(input())
    A = list(map(int, input().split()))
    left = [0] * N
    right = [0] * N
    for i in range(1, N):
        left[i] = gcd(left[i-1], A[i-1])
        right[-1-i] = gcd(right[-i], A[-i])
    gcds = []
    for i in range(N):
        gcds.append(gcd(left[i], right[i]))
    print(max(gcds))


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

S = input()
Q = int(input())
for i in range(Q):
  TFC = input().split()
  S = S[::-1] if TFC[0]=="1" else (TFC[2]+S if TFC[1]=="1" else S+TFC[2])
print(S)


### FIXED CODE ###

import sys
from collections import deque
def main():
  S = input()
  Q = int(input())
  r = False
  ans = deque(S)
  for l in sys.stdin:
    TFC = l.split()
    if TFC[0]=="1": r = not r
    elif TFC[1]=="1":
      if r: ans.append(TFC[2])
      else: ans.appendleft(TFC[2])
    elif TFC[1]=="2":
      if r: ans.appendleft(TFC[2])
      else: ans.append(TFC[2])
  print("".join(reversed(ans) if r else ans))

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

#!/usr/bin/env python3

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    cities_l = [set() for i in range(n+1)]
    cities_r = [set() for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        cities_l[l].add(i)
        cities_r[r].add(i)

    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        set_l = set()
        set_r = set()
        for j in range(qp, qq+1):
            set_l |= cities_l[j]
            set_r |= cities_r[j]
        print(len(set_l & set_r))

if __name__=='__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]
    z = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        x[l][r] += 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            c[i][j] = c[i][j-1] + x[i][j]

    for j in range(1, n+1):
        for i in range(1, n+1):
            z[i][j] = z[i-1][j] + c[i][j]
    
    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(z[qq][qq] - z[qq][qp-1] - z[qp-1][qq] + z[qp-1][qp-1])


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

N,C=map(int,input().split())
Time=[[0]*(10**5+1)]*C
for i in range(N):
  s,t,c=map(int,input().split())
  T_c=list(Time[c-1])
  T_c[s-1:t]=[1]*(t-s+1)
  Time[c-1]=list(T_c)
Times=max(map(sum,zip(*Time)))
print(Times)

### FIXED CODE ###

N,C=map(int,input().split())
Time=[[0]*(10**5+1) for c in range(C)]
for i in range(N):
  s,t,c=map(int,input().split())  
  Time[c-1][s-1:t] = [1]*(t-s+1)
Times=max(map(sum,zip(*Time)))
print(Times)
### BUGGY CODE ###

n = int(input())
ans = 0
aaa = 2
maxi = 2
def prime(aaa):
    if n != 1:
        i = 2
        while i*i <= aaa:
            if aaa % i == 0:
                return False
            i += 1
        return True
    else:
        return False
def make_divisors(n):
    if prime(n):
        return True
    a = 0
    i = 2
    while i <= n:
        if n % i == 0:
            if a == 0:
                a = i
                n /= i
                i -= 1
                if n == 1:
                    return True
            elif a == i:
                n /= i
                i -= 1
                if n == 1:
                    return True
                pass
            else:
                return False
        i += 1
    return True
def divisors(a, i):
    global ans, aaa, maxi
    while i <= n and i <= a:
        if a % i == 0:
            if make_divisors(i):
                ans += 1
                num = a / i
                aaa = num
                if maxi <= i:
                    maxi = i
                divisors(num, i+1)
                break
        i += 1
if n == 1:
    print(0)
else:
    if prime(n):
        print(1)
    else:
        divisors(n, 2)
        print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
aaa = 2
maxi = 2
def prime(aaa):
    global primemode
    if n != 1:
        i = 2
        while i*i <= aaa:
            if aaa % i == 0:
                primemode = False
                return False
            i += 1
        return True
    else:
        return False
def make_divisors(n):
    if prime(n):
        return True
    a = 0
    i = 2
    while i <= n:
        if n % i == 0:
            if a == 0:
                a = i
                n /= i
                i -= 1
                if n == 1:
                    return True
            elif a == i:
                n /= i
                i -= 1
                if n == 1:
                    return True
                pass
            else:
                return False
        i += 1
    return True
def divisors(a, i):
    global ans, aaa, maxi, primemode
    while i <= n and i <= a:
        if i * i <= a and primemode:
            if prime(a):
                ans += 1
                break
        if a % i == 0:
            if make_divisors(i):
                primemode = True
                ans += 1
                num = a / i
                aaa = num
                if maxi <= i:
                    maxi = i
                divisors(num, i+1)
                break
        i += 1
if n == 1:
    print(0)
else:
    if prime(n):
        print(1)
    else:
        divisors(n, 2)
        print(ans)
### BUGGY CODE ###

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

now=1
flg = 0
path=[1]
for i in range(k):
    now = a[now-1]
    if now in path:
        flg = -1
        path.append(now)
        break
    path.append(now)

if flg == 0:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])



### FIXED CODE ###

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

now=1
flg = 0
path = [1]
pathcheck ={1}
for i in range(k):
    now = a[now-1]
    if now in pathcheck:
        flg = -1
        path.append(now)
        break
    path.append(now)
    pathcheck.add(now)


if flg == 0:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])
### BUGGY CODE ###

N, M = map(int, input().split(" "))
stores = []
for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    tg_idx = -1
    for idx, s in enumerate(stores):
        if s[0] > Ai:
            tg_idx = idx
            break
    if tg_idx != -1:
        stores.insert(tg_idx, (Ai, Bi))
    else:
        stores.append((Ai, Bi))

    stock = 0
    unuse_idx = -1
    for idx, s in enumerate(stores):
        if stock <= M:
            stock += s[1]
        else:
            unuse_idx = idx
    if unuse_idx != -1:
        stores = stores[:unuse_idx]

price = 0
for store in stores:
    if M <= store[1]:
        price += store[0] * M
        break
    else:
        price += store[0] * store[1]
        M -= store[1]
print(price)


### FIXED CODE ###

N, M = map(int, input().split(" "))
stores = []

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stores.append((Ai, Bi))    

price = 0
for a, b in sorted(stores, key=lambda x: x[0]):
    if M <= b:
        price += a * M
        break
    else:
        price += a * b
        M -= b
print(price)
### BUGGY CODE ###

d = 10 ** 9 + 7
n = int(input())

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

s = 0
for i in range(n):
    b = 0
    for j in range(i + 1,n):
        b += a[j]
        b %= d
    c = a[i] % d
    s += c * b
    s %= d

print(s)


### FIXED CODE ###

d = 10 ** 9 + 7
n = int(input())

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


s = 0
for i in range(n):
    s += a[i]
    s %= d

ans = 0

b = 0
for i in range(n):
    b += a[i] ** 2
    b %= d

ans = s ** 2 - b
ans %= d

if ans % 2 == 0:
    ans //= 2
else:
    ans += d
    ans //= 2

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

def f3(n):
    a=b=c=0
    for _ in range(n):
        a,b,c=a+b+c+1,a,b
    return a
    
def f5(n):
    a=b=c=d=e=0
    for _ in range(n):
        a,b,c,d,e=a+b+c+d+e+1,a,b,c,d
    return a

while 1:
    s=input()
    if s=="#":break
    ans=1
    num="_"
    cnt=1
    for n in s+"_":
        if n==num:
            cnt+=1
        else:
            if num in "80":
                ans*=f3(cnt)
            else:
                ans*=f5(cnt)
            num=n
            cnt=1
    print(ans%100000007)
                
            
        
        


### FIXED CODE ###

def f3(n):
    a=b=c=0
    for _ in range(n):
        a,b,c=(a+b+c+1)%100000007,a,b
    return a
    
def f5(n):
    a=b=c=d=e=0
    for _ in range(n):
        a,b,c,d,e=(a+b+c+d+e+1)%100000007,a,b,c,d
    return a

while 1:
    s=input()
    if s=="#":break
    ans=1
    num="_"
    cnt=1
    for n in s+"_":
        if n==num:
            cnt+=1
        else:
            if num in "80":
                ans=ans*f3(cnt)%100000007
            else:
                ans=ans*f5(cnt)%100000007
            num=n
            cnt=1
    print(ans)
### BUGGY CODE ###

from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wl,vl=[],[]
wsum=0
for i in range(n):
  wn,v=map(int, input().split())
  wl.append(wn)
  vl.append(v)
  wsum+=w
if wsum<w:
  w=wsum

dp=[[0]*(w+1) for i in range(n+1)]
wmin=min(wl)

for wsum in range(wmin,w+1):
  #print("重さ：{}".format(wsum))
  for i in range(n):
    #print("i={}".format(i))
    if wsum-wl[i]>=0:
      if dp[i+1][wsum] < dp[i][wsum-wl[i]]+vl[i]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
    else:
      dp[i+1][wsum] = dp[i][wsum]
    #pprint(dp)
dp=np.array(dp)
print(np.max(dp))
      

### FIXED CODE ###

from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)
### BUGGY CODE ###

import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
  B = A[-1]//2
  del A[-1]
  bisect.insort_left(A, B)
  #print(A)
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A) #落としたりするのもO(N)かかってしまうのでHeapで実装
#A=[i for i in range(N)]
for i in range(M):
  B = heapq.heappop(A)
  heapq.heappush(A,-1*(-1*B//2))
  #print(A)
print(-sum(A))