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

import sys

iT = int(input())
aR = [[int(x) for x in sLine.split()] for sLine in sys.stdin.readlines()]
#わからんから解説見た。解説見たけどgcdの下りが自分で導出できんかったのでとりあえずバカループでなんとかしてみた。これで通るかな。
def f調1(iA,iB,iC,iD):
    if iA < iB or iD < iB:
        return False
    if iC >= iB :
        return True
    iJ = iA % iB
    iK = iD % iB
    i = 1
    while True:
        j = iJ + i * iK
        if iB <= j:
            return True
        else:
            if iC < j:
                return False
        if iK == 0:
            return True
        i += 1
    return True

for eR in aR:
    if f調1(*eR) :
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys

iT = int(input())
aR = [[int(x) for x in sLine.split()] for sLine in sys.stdin.readlines()]

def fGcd(iX,iY):
    while iY:
        iX,iY= iY,iX%iY
    return iX

#これものすごくわりきってるけど通るのか？

def fFunc(iA,iB,iC,iD):
    if iA < iB or iD < iB:
        return False
    elif iC >= iB :
        return True
    elif iC < iA % iB :
        return False
    elif iB -iC - 1 < fGcd(iB,iD) :
        return True
    else:
        return False

for eR in aR:
    if fFunc(*eR) :
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32

YES = "YES"  # type: str
NO = "NO"  # type: str

def solve(N: int, D: "List[int]", M: int, T: "List[int]"):
    
    D.sort()
    T.sort()

    from bisect import bisect_left, bisect_right

    for i in range(M):
        lf = bisect_left(D, T[i])
        ri = bisect_right(D, T[i])
        if lf != ri:
            D.pop(lf)
        else:
            print(NO)
            exit()

    print(YES)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    M = int(next(tokens))  # type: int
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, D, M, T)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

d_li.sort()
t_li.sort()

check = 0

for i in range(n):
    if d_li[i] == t_li[check]:
        check += 1
        
    if check == m:
        print("YES")
        exit()
else:
    print("NO")
### BUGGY CODE ###

n=int(input())
ans=0
l=[x for x in range(1,n+1)]
for i in range(n):
  ans+=sum(l[i::i+1])
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
  num=n//i
  k=num*i*(num+1)
  ans+=k//2
print(ans)
### BUGGY CODE ###

from itertools import product

N = int(input())

for h, n in product(range(1, 3501), range(1, 3501)):
    if ((4 * h * n) - (N * n) - (N * h)) > 0:
        if (N * h * n) % ((4 * h * n) - (N * n) - (N * h)) == 0:
            print(h, n, (N * h * n) // ((4 * h * n) - (N * n) - (N * h)))
            break

### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if ((4 * h * n) - (N * n) - (N * h)) > 0:
            if (N * h * n) % ((4 * h * n) - (N * n) - (N * h)) == 0:
                print(h, n, (N * h * n) // ((4 * h * n) - (N * n) - (N * h)))
                exit()
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
b = [k]*n
for i in a:
    b = [b[j] if i-1==j else b[j]-1 for j in range(n)]
for i in b:
    print('Yes' if i>0 else 'No')

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
b = [k]*n
for i in a: b[i-1] += 1
for i in b: print('Yes' if i>q else 'No')
### BUGGY CODE ###

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


import bisect

for _ in range(m):
    b,c = map(int,input().split())

    index = bisect.bisect_left(cards,c)

    for i in range(index):
        if i+1>b:
            continue
        cards[i]=c

    cards=sorted(cards)
    
print(sum(cards))


### FIXED CODE ###

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

from collections import Counter

d = dict(Counter(cards))

for _ in range(m):
    b,c = map(int,input().split())

    if c in d:
        d[c]+=b
    else:
        d[c]=b

d= sorted(d.items(),key=lambda x: x[0],reverse=True)

ans = 0
cnt = 0
for j in d:
    cnt +=j[1]
    ans +=j[0] * j[1]



    if cnt>n:
        ans -=j[0]*(cnt-n)
        print(ans)
        exit(0)

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

def main():
    N = int(input())
    for i in range(1, N):
        N *= i
    print(N % (10 ** 9 + 7) )


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    for i in range(1, N):
        N = N * i % (10 ** 9 + 7)
    print(N)


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

A, B, C, K = map(int, input().split())

count = 0
second = K-A-B

if A >= K:
  count = K
else:
  count = A

if second:
  for j in range(second):
    count -= 1

print(count)
  

### FIXED CODE ###

A, B, C, K = map(int, input().split())

count = 0
second = K-A-B

if A >= K:
  count = K
else:
  count = A

if second > 0:
    count -= second

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

# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
# b, c = map(int, input().split())
# スペース区切りの整数の入力
strs = input().split()
zyousi = []
for s in strs:
    zyousi.append(int(s))

for i in range(a-1):
    buka_num = 0
    for j in range(i, a-1):
        # print(j)
        if i+1 == zyousi[j]:
            buka_num += 1
    print(buka_num)
print(0)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
# b, c = map(int, input().split())
# スペース区切りの整数の入力
strs = input().split()

buka_nums = []
for i in range(a):
    buka_nums.append(0)

zyousi = []
for s in strs:
    zyousi_n = int(s)
    buka_nums[zyousi_n - 1] += 1

for i in buka_nums:
    print(i)
### BUGGY CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=list(input().split())
    i=int(query[0])
    if i==1:
        direction=direction^1
    elif i==2:
        f,c=int(query[1]),query[2]
        if f==1 and direction==0:
            s.appendleft(c)
        elif f==1 and direction==1:
            s.append(c)
        elif f==2 and direction==0:
            s.append(c)
        elif f==2 and direction==1:
            s.appendleft(c)

if direction==0:
    print(*s,sep='')
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(*x,sep='')


### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=input()
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        i,f,c=query.split()
        if f=='1' and direction==0:
            s.appendleft(c)
        elif f=='1' and direction==1:
            s.append(c)
        elif f=='2' and direction==0:
            s.append(c)
        elif f=='2' and direction==1:
            s.appendleft(c)


if direction==0:
    print(''.join(s))
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(''.join(x))
### BUGGY CODE ###

import heapq

n, x, y = map(int, input().split())

Edge = [[] for _ in range(n+1)]
for i in range(1,n):
    Edge[i].append([1, i+1])
    Edge[i+1].append([1, i])

Edge[x].append([1,y])
Edge[y].append([1,x])

def dijkstra_heap(s):
    # 始点sから各頂点への最短距離
    d = [10**10] * (n+1)
    used = [False] * (n+1)
    d[s] = 0
    used[s] = True
    edgelist = []
    
    # edgeは各頂点の[重み、行先]からなる配列
    for e in Edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)

        # 未使用の頂点から最小の距離のものを探す
        if used[minedge[1]] == True:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True

        for e in Edge[v]:
            if used[e[1]] == False:
                heapq.heappush(edgelist, [e[0]+d[v], e[1]])
    return d

Ans = [0 for _ in range(n+1)]
for i in range(1,n):
    Dist = dijkstra_heap(i)
    # print(Dist)
    for dist in Dist[i:]:
        Ans[dist] += 1

for i in range(1,n):
    print(Ans[i])


### FIXED CODE ###

import heapq

n, x, y = map(int, input().split())

Edge = [[] for _ in range(n+1)]
for i in range(1,n):
    Edge[i].append([1, i+1])
    Edge[i+1].append([1, i])

Edge[x].append([1,y])
Edge[y].append([1,x])

def dijkstra_heap(s):
    # 始点sから各頂点への最短距離
    d = [10**10] * (n+1)
    used = [False] * (n+1)
    d[s] = 0
    used[s] = True
    edgelist = []
    
    # edgeは各頂点の[重み、行先]からなる配列
    for e in Edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)

        # 未使用の頂点から最小の距離のものを探す
        if used[minedge[1]] == True:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True

        for e in Edge[v]:
            if used[e[1]] == False:
                heapq.heappush(edgelist, [e[0]+d[v], e[1]])
    return d

Ans = [0 for _ in range(n+1)]
for i in range(1,n):
    Dist = dijkstra_heap(i)
    # print(Dist)
    for dist in Dist[i:]:
        Ans[dist] += 1

for i in range(1,n):
    print(Ans[i])
### BUGGY CODE ###

import math
mf=math.floor
a,b,n=map(int,input().split())
d=0
for i in range(n+1):
    c=mf(a*i/b)-a*mf(i/b)
    d=max(d,c)
print(d)


### FIXED CODE ###

import math
mf=math.floor
a,b,n=map(int,input().split())
d=0
if n<b:
    i=n
elif n>=b:
    i=b-1
c=mf(a*i/b)-a*mf(i/b)
print(c)
### BUGGY CODE ###

from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if [i + 1, j + 1] not in hw:
            print(max_h + max_w)
            exit()

print(max_num)


### FIXED CODE ###

H, W, M = map(int, input().split())
hw = set()
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.add((h, w))
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if (i + 1, j + 1) not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        return find_head(tree[i])
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        tree[i] = find_head(tree[i])
        return tree[i]
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)
### BUGGY CODE ###

from math import floor


def solve(n, m):
    ans = 0
    if m % n == 0:
        ans = m // n
    else:
        factor = [f for f in range(1, floor(m//n)) if m % f == 0]
        if len(factor) > 0:
            ans = factor[-1]
        else:
            ans = 1

    return ans


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve(n, m))


### FIXED CODE ###

from math import floor


def solve(n, m):
    factor = [1]
    if m % n == 0:
        ans = m // n
    else:
        for f in range(floor(m//n), 1,-1):
            if m % f == 0:
                factor.append(f)
                break
        ans = factor[-1]

    return ans


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve(n, m))
### BUGGY CODE ###

H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            fin += 1
        else:
            cnt[h][w] = -1

            
#print(cnt,fin)
dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    for h in range(1,H+1):
        for w in range(1,W+1):
            if cnt[h][w] == c:
                for dx,dy in dxy:
                    if cnt[h+dx][w+dy] == -1:
                        cnt[h+dx][w+dy] = c+1
                        #print(cnt)
                        fin += 1
    c += 1

print(c)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
st = deque()
sts = deque()
push, pop = st.append, st.pop
pushs, pops = sts.append, sts.pop
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            push([h,w])
            fin += 1
        else:
            cnt[h][w] = -1


dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    while st:
        [h,w] = pop()
        for dx,dy in dxy:
            if cnt[h+dx][w+dy] == -1:
                #print(c,fin)
                cnt[h+dx][w+dy] = c+1
                pushs([h+dx,w+dy])
                fin += 1
    c += 1
    while sts:
        [h,w] = pops()
        push([h,w])


print(c)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

res = float('inf')
for i in range(2**(H-1)):
    c = bin(i).count('1')
    cnt = c
    sum_l = [0] * (c+1)
    j = 0
    while j < W:
        tmp = sum_l.copy()
        pos = 0
        for k in range(H):
            if S[k][j] == '1':
                tmp[pos] += 1
            if (i >> k) & 1:
                pos += 1
        if max(tmp) <= K:
            sum_l = tmp.copy()
            j += 1
        else:
            cnt += 1
            sum_l = [0] * (c+1)

    res = min(res, cnt)

print(res)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

res = float('inf')
for i in range(2**(H-1)):
    c = bin(i).count('1')
    cnt = c
    sum_l = [0] * (c+1)
    j = 0
    flag = True
    while j < W:
        tmp = sum_l.copy()
        pos = 0
        for k in range(H):
            if S[k][j] == '1':
                tmp[pos] += 1
            if (i >> k) & 1:
                pos += 1
        if max(tmp) <= K:
            sum_l = tmp.copy()
            j += 1
            flag = False
        else:
            if flag:
                cnt = float('inf')
                break
            cnt += 1
            flag = True
            sum_l = [0] * (c+1)

    res = min(res, cnt)

print(res)
### BUGGY CODE ###

N = int(input())
lista = sorted(list(map(int, input().split())))
length = len(lista)
while length>1:
    #print(length)
    #print(lista)
    for n in range(1, length):
        lista[n] = lista[n]%lista[0]
    #print(lista)
    lista.sort()
    #print(lista)
    lista = list(set(lista))
    if lista[0] == 0:
        lista.remove(0)
    #print(lista)
    length = len(lista)
print(lista[0])  

### FIXED CODE ###

N = int(input())
lista = sorted(list(map(int, input().split())))
length = 2
while length>1:
    #print(length)
    #print(lista)
    for n in range(1, length):
        lista[n] = lista[n]%lista[0]
    #print(lista)
    lista = list(set(lista))
    lista.sort()
    if lista[0] == 0:
        lista.remove(0)
    #print(lista)
    length = len(lista)
print(lista[0])
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=tuple(map(int,input().split()))
b=tuple(map(int,input().split()))
c=tuple(map(int,input().split()))
 
def f(p,q):
    return [i+j for j in q for i in p]
 
if x+y<y+z:
    for i in sorted(f(c,f(a,b)))[::-1][:k]:
        print(i)
elif x+z<y+z:
    for i in sorted(f(b,f(a,c)))[::-1][:k]:
        print(i)
else:
    for i in sorted(f(a,f(b,c)))[::-1][:k]:
        print(i)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
 
AB = sorted([a + b for a in A for b in B])[-1:-K-1:-1]
ABC = sorted([ab + c for ab in AB for c in C])[-1:-K-1:-1]
print('\n'.join(map(str, ABC)))
### BUGGY CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	for i in range(1,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j].insert(0,0)
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4].insert(0,0)
				else: break
				m+=1
			ans = max(ans,a)
print(ans)

### FIXED CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	if h==30: z = 25
	else: z = h//2
	for i in range(z,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j].insert(0,0)
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4].insert(0,0)
				else: break
				m+=1
			ans = max(ans,a)
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
mod=1000000000000000000
ans=1
p=1
l.sort()
for i in range(0,n):
  x=l[i]
  p=p*x
  if(x==0):
    ans=0
    break
if(p>mod):
    ans=-1
if(ans!=0 and ans!=-1):
  ans=p
print(ans)
  
  


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
mod=1000000000000000000
ans=1
p=1
if(l.count(0)>=1):
    ans=0
else:
    for i in range(0,n):
        x=l[i]
        p=p*x
        if(p>mod):
            ans=-1
            break
if(ans!=0 and ans!=-1):
    ans=p
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
S=sum(a)
for i in range(n):
    a[i]*=2
ans=[]
for i in range(n):
    rmv=0
    for j in range(n//2):
        k=(i+2*j+1)%(n)
        rmv+=a[k]
    ans.append(S-rmv)
for i in range(n):
    ans[i]=str(ans[i])
print(' '.join(ans))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
b_1=0
for i in range(n):
    if i%2==0:
        b_1+=a[i]
    else:
        b_1-=a[i]
ans.append(str(b_1))
for i in range(1,n):
    ans.append(str(a[i-1]*2-int(ans[-1])))
print(' '.join(ans))
### BUGGY CODE ###

#141d
from collections import deque
import bisect
import math

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list)>1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    while 1:
        #print(A_list,highest)
        
        #highest/(pow(2,X)) <= next_highest に持っていきたい
        #highest <= next_highest * pow(2,X)
        #highest/next_highest <= 2**X
        #log2(highest/next_highest) <= X
        use_tickets = math.ceil(math.log2(highest/next_highest))
        if use_tickets == 0:
            use_tickets = 1
        if use_tickets > M:
            use_tickets = M
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        #print(A_list,highest)
        
        if M!= 0:
            bisect.insort(A_list,highest)
            highest = A_list.pop()
            next_highest = A_list[-1]
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    print(sum(A_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])


### FIXED CODE ###

#141d
from collections import deque
import bisect
import math

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list) > 1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    discounted_deque = deque()

    while 1:
        use_tickets = math.ceil(math.log(highest/next_highest)/math.log(2))
        if use_tickets == 0:
            use_tickets = 1
        elif use_tickets > M:
            use_tickets = M
            
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        if M!= 0:
            discounted_deque.appendleft(highest)
            
            if len(A_list) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    highest = A_list.pop()
                else:
                    highest = discounted_deque.pop()
            else:
                highest = discounted_deque.pop()
                
            if len(A_list) > 0 and len(discounted_deque) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    next_highest = A_list[-1]
                else:
                    next_highest = discounted_deque[-1]
            elif len(A_list) == 0 and len(discounted_deque) > 0:
                next_highest = discounted_deque[-1]
            elif len(A_list) > 0 and len(discounted_deque) == 0:
                next_highest = A_list[-1]
            
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    discounted_list = [int(B) for B in discounted_deque]
    
    print(sum(A_list)+sum(discounted_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])