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

from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,qA)
            if w:
                break
            qA.popleft()            
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        Ac = deque(list(A))
        Ad = deque(list(A))
        m_new = m
        if m_new < 0:
            r1 = False
        elif m_new == 0:
            r1 = True
        else:
            if len(A) == 1:
                r1 = False
            else:
                Ac.popleft()
                r1 = self.rec(m_new,Ac)
        m_new = m - Ad[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        else:
            if len(A) == 1:
                r2 = False
            else:
                Ad.popleft()
                r2 = self.rec(m_new,Ad)
        if r1 or r2:
            return True
        else:
            return False
if __name__ == "__main__":
    MC = MyClass()
    MC.main()

### FIXED CODE ###

from collections import deque

def main():
    n = input()
    A = deque(map(int,raw_input().split()))
    q = input()
    M = map(int,raw_input().split())

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

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

from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A[:i],b)
        if ind<i and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and hist[ind]==1:
            ind += 1
            while A[ind]==b and ind<i:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
                ind += 1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
A = [[A[i],0] for i in range(N)]
cnt = 0
for i in range(N-1,0,-1):
    if A[i][1]==0:
        a = A[i][0]
        A[i][1]=1
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,[b,1])
        ind -= 1
        if ind<i and A[ind]==[b,0]:
            A[ind][1]=1
            cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()

pin = [str(i).zfill(3) for i in range(1000)]

ans = 0
for i in pin:
    c = 0
    for j in s:
        if j == i[c]:
            c += 1
        if c == 3:
            ans += 1
            break
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

pins = [str(i).zfill(3) for i in range(1000)]

ans = 0
for pin in pins:
    index = -1;
    for c in pin:
      index = s.find(c, index+1);
      if (index < 0):
        break;
    if (index > 0):
      ans += 1;
      
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

input = sys.stdin.readline

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

tile = {} # 文字マップ
now = np.array([1] * (N+2))

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i+1)

for i in range(Q):
  t, d = input().split()
  old = now[tile[t]]
  if d == "L":
    now[(np.array(tile[t])-1).tolist()] += old
    now[tile[t]] -= old
  else:
    now[(np.array(tile[t])+1).tolist()] += old
    now[tile[t]] -= old

#print(now)
print(sum(now) - now[0] - now[-1])

### FIXED CODE ###

# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N
for i in range(N):
  w, v = map(int, input().split()) 
  ws[i] = w
  vs[i] = v

dp = np.zeros((N+1, W+1), dtype='uint64')
  
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(max(dp[N, :]))
  

### FIXED CODE ###

import numpy as np

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

dp = np.zeros((N+1, W+1), dtype='uint64')

for i in range(N):
  w, v = map(int, input().split()) 
  dp[i+1][:w] = dp[i][:w]
  dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
print(np.max(dp[N]))
### BUGGY CODE ###

import itertools

N, K = list(map(int, input().split()))
p_n = list(map(int, input().split()))
ans = 10 ** 10

for p in itertools.combinations(p_n, K):
    s = sum(p)
    if ans > s:
        ans = s

print(ans)

### FIXED CODE ###

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

for i in range(K):
    ans += p_n[i]

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

n,*s=map(str,open(0).read().split())
mydict={}
for i in range(int(n)):
    if s[i] in mydict:
        mydict[s[i]]+=1
    else:
        mydict[s[i]]=1
for j in sorted([kv[0] for kv in mydict.items() if kv[1]==max(mydict.values())]):
    print(j)

### FIXED CODE ###

n,*s=map(str,open(0).read().split())
mydict={}
for i in set(s):
    mydict[i]=1
for i in s:
    mydict[i]+=1
    """
    if s[i] in mydict:
        mydict[s[i]]+=1
    else:
        mydict[s[i]]=1
    """
v_max=max(mydict.values())
for i in sorted([kv[0] for kv in mydict.items() if kv[1]==v_max]):
    print(i)
### BUGGY CODE ###

S=input()
l=len(S)
t=0
p=0
m=[0] * l

for i in range(l):
    m[i]=int(S[i])*(10**(l-1-i))%2019

for i in range(l):
    p=0
    for j in range(l-i):
        p=(p+m[i+j])%2019
        if p==0:
            t+=1
print(t)



### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

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

num, d = 0, 1

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

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

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

import copy

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

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)

def score(A):
	return(sum(A)-len(A))

def Ifavor(A):
	return(score(A)%2==1)	

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	
def testmove(A,i):
	B=copy.deepcopy(A)
	N=len(B)
	playmove(B,i)
	if Ifavor(B):
		return('False')
	else:
		e=0
		while e<N:
			C=copy.deepcopy(B)
			playmove(C,e)
			e+=1
			if Ifavor(C)==False:
				return(False)
		return('True')
	

N=int(input())
A=[int(x) for x in input().split()]
#inp=St.splitlines()
#N=int(inp[0])
#A=[int(x) for x in inp[1].split()]

B=copy.deepcopy(A)


if Ifavor(B):
	print('First')
else:
	maxply=sum(B)-N
	ply=1
	while min(B)>1 and ply<=maxply:
		e=0
		while e<N:
			if testmove(B,e):
				break
			e+=1
			
		if e==N:
			break
		else:
			playmove(B,e)
			ply+=1

	if (ply%2==1)!=Ifavor(B):
		print('Second')
	else:
		print('First')

### FIXED CODE ###

import random
def tester(N=0):
	'''制約
1≦N≦105
1≦Ai≦109
'''
	maxno1=1e5
	maxno2=1e9
	s=input()
	if s!='':return(s)
	
	if N==0:
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		return(' '.join(list(map(str,A))))

import copy

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

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		if g==1:
			return(g)
		g=gcd(g,x[i])
	return(g)

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	return([x//g for x in A])

def noofevens(A):
	r=0
	for i in A:
		if i%2==0:
			r+=1
	return(r)
			

N=int(tester())
A=[int(x) for x in tester(N).split()]


isFirstmove=True
while True:
	e=noofevens(A)
	if e%2==1:
		if isFirstmove:
			print('First')
		else:
			print('Second')
		break
	elif N-e>1:
		if isFirstmove:
			print('Second')
		else:
			print('First')
		break
	else:	
		for i in range(N):
			if A[i]%2==1:
				break
		if A[i]==1:
			if isFirstmove:
				print('Second')
			else:
				print('First')
			break
		else:
			A=playmove(A,i)
			isFirstmove=(isFirstmove!=True)
### BUGGY CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
c = collections.Counter(A)
num = len(c)
for i in range(len(c)):
  if c.most_common()[i][1]%2 == 0:
    num -= 1
print(num)

### FIXED CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
c = collections.Counter(A)
num = 0
for i,j in c.items():
  if j%2 != 0:
    num += 1
print(num)
### BUGGY CODE ###

#ずっとre
from fractions import gcd
from functools import reduce

def get_gcd(number_list):
    return reduce(gcd, number_list)

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

gcd_list = [0] * N
for i in range(N):
    tmp_list = Numbers[:i] + Numbers[i + 1:]
    gcd_list[i] = get_gcd(tmp_list)
    
print(int(max(gcd_list)))

### FIXED CODE ###

from functools import reduce
from itertools import combinations
from fractions import gcd

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


Left = [0] * (N + 1)
Right = [0] * (N + 1)

for i in range(N):
    Left[i + 1] = gcd(Left[i], A[i])
    Right[N - i - 1] = gcd(Right[N - i], A[N - i - 1])
ans = 0
for i in range(N):
    ans = max(ans, gcd(Left[i], Right[i + 1]))
    
print(ans)
### BUGGY CODE ###

import queue as qu
import numpy as np
import functools as ft

words = lambda t : np.array(list(map(t, input().split())))

h,w = words(int)
mat = []
for _ in range(h):
    a = np.array(list(input()))
    mat.append(a)

mat = np.array(mat)
#print(mat)

prev = []
for i in range(h):
    for j in range(w):
        if mat[i][j] == "#":
            prev.append((i,j))

def putL(x, y, next):
    if x != 0 and mat[x-1][y] != "#":
        next.append((x-1,y))
        mat[x-1][y] = "#"
    if y != 0 and mat[x][y-1] != "#":
        next.append((x,y-1))
        mat[x][y-1] = "#"
    if x != h-1 and mat[x+1][y] != "#":
        next.append((x+1,y))
        mat[x+1][y] = "#"
    if y != w-1 and mat[x][y+1] != "#":
        next.append((x,y+1))
        mat[x][y+1] = "#"

round = -1
while not len(prev) == 0:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        putL(x, y, next)

    prev = next

print(round)


### FIXED CODE ###

import functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    #print(prev)
    #print(mat)
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
c = []
c.append(['×' for _ in range(w+2)])
for _ in range(h):
	c.append(list('×'+input()+'×'))
c.append(['×' for _ in range(w+2)])
ans = [[101 for _ in range(w+2)]for _ in range(h+2)]
if c[1][1] == '.':
	ans[1][1] = 0
else:
	ans[1][1] = 1

q = deque()

def bfs(x,y):
	global q
	global c
	q.append([x,y])

	while q:
		x,y = q.popleft()

		if [x,y] == [w,h]:
			return ans[h][w]
		if c[y][x+1] == '.':
			q.append([x+1,y])
			#c[y][x+1] = '×'
			if ans[y][x+1] == 101:
				ans[y][x+1] = ans[y][x]
			else:
				ans[y][x+1] = min(ans[y][x+1],ans[y][x])
		elif c[y][x+1] == '#':
			q.append([x+1,y])
			#c[y][x+1] = '×'
			if ans[y][x+1] == 101:
				ans[y][x+1] = ans[y][x] + 1
			else:
				ans[y][x+1] = min(ans[y][x+1],ans[y][x]+1)
		if c[y+1][x] == '.':
			q.append([x,y+1])
			#c[y+1][x] = '×'
			if ans[y+1][x] == 101:
				ans[y+1][x] = ans[y][x]
			else:
				ans[y+1][x] = min(ans[y+1][x],ans[y][x])
		elif c[y+1][x] == '#':
			q.append([x,y+1])
			#c[y+1][x] = '×'
			if ans[y+1][x] == 101:
				ans[y+1][x] = ans[y][x] + 1
			else:
				ans[y+1][x] = min(ans[y+1][x],ans[y][x]+1)


print(bfs(1,1))


### FIXED CODE ###

h,w = map(int,input().split())

s = []
for _ in range(h):
	s.append(list(input()))

inf = float('inf')
dp = [[inf for _ in range(w)] for _ in range(h)]
dp[0][0] = 0

for i in range(h):
	for j in range(w):
		if s[i][j] == ".":
			if j > 0 and i > 0:
				dp[i][j] = min(dp[i-1][j],dp[i][j-1])
			elif j > 0 and i == 0:
				dp[i][j] = dp[i][j-1]
			elif j == 0 and i > 0:
				dp[i][j] = dp[i-1][j]
		else:
			tmp1 = inf
			tmp2 = inf
			if i > 0:
				tmp1 = dp[i-1][j]
				if s[i-1][j] == ".":
					tmp1 += 1
			if j > 0:
				tmp2 = dp[i][j-1]
				if s[i][j-1] == ".":
					tmp2 += 1
			dp[i][j] = min(tmp1,tmp2)
			if i==0 and j==0:
				dp[i][j] = 1

print(dp[h-1][w-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S.add(i)

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1, N):
    if dp[i] == 0:
        continue
    for s in S:
        if i + s <= N:
            dp[s+i] += dp[i]
            dp[s+i] %= mod

print(dp[N])

### FIXED CODE ###

import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S.add((l, r))

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
acc = [0 for _ in range(N+1)]
acc[1] = 1
for i in range(1, N+1):
    for (l, r) in S:
        left = max(i - r - 1, 0)
        right = max(i - l, 0)
        # print("left", left, "right", right)
        dp[i] += acc[right] - acc[left]
        dp[i] %= mod
    acc[i] = acc[i-1] + dp[i]
    acc[i] %= mod

# print(acc)
print(dp[N])
### BUGGY CODE ###

K = N = int(input())
C = input()
pre = [0 for _ in range(2*10**5+1)]

for i in range(2*10**5+1):
    N = i
    ans = 0
    while N > 0:
        cnt = 0
        for c in format(N,"b"):
            if c == "1":
                cnt += 1
        N %= cnt
        ans += 1
    pre[i] = ans


for i in range(K):
    if C[i] == "1":
        X = C[:i] + "0" + C[i+1:]
    else:
        X = C[:i] + "1" + C[i+1:]

    if int(X, 2) > 2*10**5:
        cnt = 0
        for c in format(int(X, 2),"b"):
            if c == "1":
                cnt += 1
        print(pre[int(X, 2) % cnt] + 1)
    else:
        print(pre[int(X,2)])

### FIXED CODE ###

n = int(input())
x = input()

def count(n):
    cnt = 0
    while n:
        cnt += n % 2
        n //= 2
    return cnt

LIMIT = 5*10**5
dp = [0] * LIMIT
for i in range(1, LIMIT):
    dp[i] = dp[i % count(i)]+1

c = x.count("1")
a = int(x,2) % (c+1)

if c == 1:
    for i in range(n):
        if x[i] == "0":
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
        else:
            print(0)
    exit()

b = int(x,2) % (c-1)
for i in range(n):
    if x[i] == "0":
        print(dp[(a + pow(2, n-i-1, c + 1)) % (c + 1)] + 1)
    else:
        print(dp[(b - pow(2, n-i-1, c - 1)) % (c - 1)] + 1)
### BUGGY CODE ###

from collections import deque
S=input()
s=deque(S)
Q=int(input())
Que=[list(map(str, input().split())) for _ in range(Q)]
#print(Que)
for i in range(Q):
    if Que[i][0]=="1":
        s.reverse()
#        s=s[::-1]
    elif Que[i][0]=="2":
        if Que[i][1]=="2":
            s.append(Que[i][2])
        elif Que[i][1]=="1":
            s.appendleft(Que[i][2])
ans="".join(s)
print(ans)


### FIXED CODE ###

from collections import deque
S=input()
s=deque(S)
Q=int(input())
Que=[list(map(str, input().split())) for _ in range(Q)]
#print(Que)
a=0
for i in range(Q):
    if Que[i][0]=="1":
        a+=1
    elif Que[i][0]=="2":
        if a%2==0:
            if Que[i][1]=="2":
                s.append(Que[i][2])
            elif Que[i][1]=="1":
                s.appendleft(Que[i][2])
        else:
            if Que[i][1]=="1":
                s.append(Que[i][2])
            elif Que[i][1]=="2":
                s.appendleft(Que[i][2])
s=list(s)
if a%2==1:
    s=s[::-1]
ans="".join(s)
print(ans)
### BUGGY CODE ###

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

B=[-1]*(N+1)

def make_buger(n):
  if n==0:
    return "P"
  else:
    if B[n-1]==-1:
      tmp=make_buger(n-1)
      B[n-1]=tmp
    else:
      tmp=B[n-1]
    tmp="B"+tmp+"P"+tmp+"B"
    B[n]=tmp
    return tmp
buger=make_buger(N)
print(buger[-X:].count("P"))

### FIXED CODE ###

N,X=map(int,input().split())
a=[1]
p=[1]
for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    if x<=a[n-1]+1:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-a[n-1]-2)+1
print(f(N,X))
### BUGGY CODE ###

h,w=map(int,input().split())

field=[]
m=[]
INF=10**4

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

dx=[1,0,-1,0]
dy=[0,1,0,-1]

queue=[]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])
while len(queue)>0:
    y,x=queue.pop(0)
    field[y][x]="#"
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
            
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i in range(h):
    for j in range(w):
        k=a[-1-i][-1-j]+1
        if i!=h-1:
            if k<a[-i-2][-j-1]:
                a[-i-2][-j-1]=k

        if j!=w-1:        
            if k<a[-i-1][-j-2]:
                a[-i-1][-j-2]=k

for i in range(h):
    ans=max(ans,max(a[i]))
print(ans)
### BUGGY CODE ###

N = int(input())
Ai = list(map(int, input(). split()))
Bi = list(map(int, input(). split()))
Ci = list(map(int, input(). split()))

Ai.sort()
Bi.sort()
Ci.sort()
count = 0

for k in range(N):
    for j in range(N):
        for i in range(N):
            if (Ci[k] > Bi[j]):
                if (Bi[j] > Ai[i]):
                    count += 1
                else:
                    break
            else:
                break
            
print(count)

### FIXED CODE ###

import bisect

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

ans = 0

for b in B:
   ans += (bisect.bisect_left(A,b)) *(N - bisect.bisect_right(C,b))

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

import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nl()
A=nl()

for i in range(M):
	A.sort()
	A[-1]=A[-1]//2

print(sum(A))   

### FIXED CODE ###

import sys
import heapq
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
h=[]
for i in A:
    heapq.heappush(h,-1*i)

for i in range(M):
	maxval=heapq.heappop(h)
	heapq.heappush(h,-(-maxval//2))
    
print(-sum(h))
### BUGGY CODE ###

N,K=map(int,input().split())
mod=10**9+7
Layer=[]
a=1
b=1
while(b<=N):
    a=b
    b=N//(N//a)+1
    Layer.append((a,b))
#print(Layer)
num=[x[1]-x[0] for x in Layer]
M=len(Layer)
#print(num)
dp=[[0 for j in range(M+1)] for i in range(K+1)]
dp[0][0]=1
sdp=[0 for i in range(M+2)]
for k in range(K):
    for j in range(M+1):
        sdp[j+1]=(dp[k][j]+sdp[j])%mod
    for j in range(M):
        dp[k+1][j]=(sdp[M-j]*num[j])%mod
ans=0
for j in range(M+1):
    ans+=dp[K][j]
    ans%=mod
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
mod=10**9+7
Layer=[]
a=1
b=1
while(b<=N):
    a=b
    b=N//(N//a)+1
    Layer.append((a,b))
#print(Layer)
num=[x[1]-x[0] for x in Layer]
M=len(Layer)
#print(num)
dp=[[0 for j in range(M+1)] for i in range(K+1)]
dp[0][0]=1
sdp=[0 for i in range(M+2)]
for k in range(K):
    for j in range(M+1):
        sdp[j+1]=(dp[k][j]+sdp[j])%mod
    for j in range(M):
        dp[k+1][j]=(sdp[M-j]*num[j])%mod
ans=0
for j in range(M+1):
    ans+=dp[K][j]
    ans%=mod
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S=input()
l=list()
r=list()
for i in range(Q):
  LandR=list(map(int,input().split()))
  l.append(LandR[0])
  r.append(LandR[1])
  S2=S[l[i]-1:r[i]].split("AC")
  print(len(S2)-1)

### FIXED CODE ###

N, Q = map(int, input().split())
S=list(input())
Snum=list()
Snum.append(0)
Snum.append(0)
for i in range(1,N):
  if S[i]=="C" and S[i-1]=="A":
    Snum.append(Snum[i]+1)
  else:
    Snum.append(Snum[i])
for i in range(Q):
  L,R=map(int, input().split())
  print(Snum[R]-Snum[L])
### BUGGY CODE ###

l,r = map(int,input().split())
ans = 100000000000000000
for i in range(l,r):
  for j in range(l+1,r+1):
    ans = min(ans,(i*j) % 2019)
print(ans) 

### FIXED CODE ###

l,r = map(int,input().split())
if r-l >= 2019:
    print(0)
else:
    r1 = r % 2019
    l1 = l % 2019
    if l1 > r1:
        print(0)
    else:
        ans = 2019
        for i in range(l1, r1):
            for j in range(i + 1, r1 + 1):
                ans = min(ans, (i*j) % 2019)
        print(ans)
### BUGGY CODE ###

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

dp = [0] * N
dp[1] = abs(H[1] - H[0])
for i in range(2,N):
    dp[i] = min(dp[i-j] + abs(H[i] - H[i-j]) for j in range(1,max(K,i)))
print(dp[-1])

### FIXED CODE ###

import sys

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

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0] * (N + 1)

    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(2,N):
        dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-K),i))
    print(dp[N-1])

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

from collections import deque
s=input()
length=len(s)

K=int(input())
#print(s,K)

left=0
right=0
#ss=s[left:right]
#print(ss)

ss=deque()
for left in range(length+1):
    for right in range(left+1,length+1):
        ss.append(s[left:right])

myset=set(ss)
for i in range(K):
    tmp=min(myset)
    myset.remove(tmp)
print(tmp)



### FIXED CODE ###

from collections import deque
s=input()
length=len(s)

K=int(input())
#print(s,K)

left=0
right=0
#ss=s[left:right]
#print(ss)

ss=deque()
for left in range(length+1):
    for right in range(left+1,length+1):
      if len(s[left:right]) <= K:
        ss.append(s[left:right])

myset=set(ss)
for i in range(K):
    tmp=min(myset)
    myset.remove(tmp)
print(tmp)