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

import bisect
import queue
INF=10**18
n=int(input())
a=queue.Queue()
for _ in range(n):
  a.put(int(input()))
cnt=0
while a.qsize():
  dp=[]
  for i in range(a.qsize()):
    i=a.get()
    if bisect.bisect_left(dp,i)==len(dp):
      dp.append(i)
    else:
      a.put(bisect.bisect_left(dp,i))
      dp[bisect.bisect_left(dp,i)]=i
  cnt+=1
print(cnt)

### FIXED CODE ###

import bisect
n=int(input())
a=[int(input()) for _ in range(n)][::-1]
dp=[]
for i in a:
  if bisect.bisect_right(dp,i)==len(dp):
    dp.append(i)
  else:
    dp[bisect.bisect_right(dp,i)]=i
print(len(dp))
### BUGGY CODE ###

import copy
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    m = 400
    dp = [[False]*(m+1) for _ in range(w)]
    dp[0][abs(a[0][0] - b[0][0])] = True
    for i in range(1, w):
        x = abs(a[0][i] - b[0][i])
        for j in range(m+1):
            if dp[i-1][j]:
                if j+x <= m:
                    dp[i][j+x] = True
                dp[i][abs(j-x)] = True
    for i in range(1, h):
        for j in range(w):
            buf = [False]*(m+1)
            x = abs(a[i][j] - b[i][j])
            for k in range(m+1):
                f = False
                if j == 0:
                    if dp[0][k]:
                        f = True
                else:
                    if dp[j-1][k] or dp[j][k]:
                        f = True
                if f:
                    if k+x <= m:
                        buf[k+x] = True
                    buf[abs(k-x)] = True
            dp[j] = copy.deepcopy(buf)
    for i in range(m+1):
        if dp[w-1][i]:
            print(i)
            break

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

import numpy as np
from collections import deque

@np.vectorize
def trans(s):
    return 1 if s == "#" else 0

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def appender(i, j, H, W, C, S, Q):
    if i + 1 < H and not C[i+1, j] and S[i, j] != S[i+1, j]:
        Q.append((i + 1, j))
    if i > 0 and not C[i-1, j] and S[i, j] != S[i-1, j]:
        Q.append((i - 1, j))
    if j + 1 < W and not C[i, j+1] and S[i, j] != S[i, j+1]:
        Q.append((i, j + 1))
    if j > 0 and not C[i, j-1] and S[i, j] != S[i, j-1]:
        Q.append((i, j - 1))

def search(S, start, C):
    Q = deque([start])
    H, W = S.shape
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if C[i, j]:
            continue
        else:
            C[i, j] = True
            if S[i, j] == 0:
                n0 += 1
            else:
                n1 += 1
            appender(i, j, H, W, C, S, Q)
    return n0, n1


def search_all(S):
    C = np.full_like(S, False).astype(np.bool)
    D = np.full_like(S, 0)
    ret = 0
    for i in range(S.shape[0]):
        for j in range(S.shape[1]):
            if D[i, j] == 0:
                n0, n1 = search(S, (i, j), C)
                D += C
                ret += n1 * n0
                if np.all(D):
                    return ret
                else:
                    C[:, :] = False



import sys
    
print(search_all(parse(sys.stdin)))

### FIXED CODE ###


import numpy as np
from collections import deque
import sys

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([list(next(inp).strip()) for _ in range(H)])

dis = [0, 0, 1, -1]
djs = [1, -1, 0, 0]

def search(S, i, j, Q, R):
    H, W = S.shape
    R[i, j] = True
    Q.append((i, j))
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if S[i, j] == "#":
            n1 += 1
        else:
            n0 += 1
        gen = ((i + di, j + dj) for di, dj in zip(dis, djs))
        ijs = (g for g in gen if 0 <= g[0] and g[0] < H and 0 <= g[1] and g[1] < W)
        for ni, nj in ijs:
            if not R[ni, nj] and S[ni, nj] != S[i, j]:
                R[ni, nj] = True
                Q.append((ni, nj))
    return n0 * n1


def test(S):
    i, j = 0, 0
    Q = deque()
    R = np.full(S.shape, False)
    H, W = S.shape
    n = 0
    for i in range(H):
        for j in range(W):
            if not R[i, j]:
                n += search(S, i, j, Q, R)
    return n

print(test(parse(sys.stdin)))
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if l == s-i-j:
                cnt += 1
            
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0

for i in range(k+1):
    for j in range(k+1):
        l = s-i-j
        if 0 <= l <= k:
            cnt += 1
            
print(cnt)
### 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()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

min_b = min(B)
max_b = max(B)
max_c = max(C)
summs = []
for a in A:
    if len(summs) >= K and a + max_b + max_c < summs[K-1]:
        break
        
    for b in B:
        if len(summs) >= K and a + b + max_c < summs[K-1]:
            break

        for c in C:
            summ = a + b + c
            if len(summs) >= K:
                min_sum = summs[K-1]    
                if summ < min_sum:
                    break
            summs.append(summ)
        summs.sort(reverse=True)

for s in summs[0:K]:
    print(s)

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
C = list(map(int, input().split()))

ans = -(10 ** 18)

for si in range(N):
    x = si
    loop = []
    total = 0
    while 1:
        x = P[x]
        loop.append(C[x])
        total += C[x]
        if x == si:
            break
    T = len(loop)  # 周期の大きさ
    tmp = 0
    for i in range(T):
        tmp += loop[i]
        if K < i + 1:
            break
        now = tmp
        if total > 0:  # loopの和が正ならloopを回した方がお得
            loop_times = (K - (i + 1)) // T  # 何周できるか
            now += total * loop_times
        ans = max(ans, now)

print(ans)



### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
C = list(map(int, input().split()))

ans = -(10 ** 18)

for si in range(N):
    x = si
    loop = []
    total = 0
    while 1:
        x = P[x]
        loop.append(C[x])
        total += C[x]
        if x == si:
            break
    T = len(loop)  # 周期の大きさ
    tmp = 0
    for i in range(T):
        tmp += loop[i]
        if K < i + 1:
            break
        now = tmp
        if total > 0:  # loopの和が正ならloopを回した方がお得
            loop_times = (K - (i + 1)) // T  # 何周できるか
            now += total * loop_times
        ans = max(ans, now)

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

r,g,b,n = map(int,input().split())

ans = 0
for i in range(n+1):
    for j in range(n+1):
        z = r * i + g * j
        if z <= n and (n - z) % b == 0:
            ans += 1
print(ans)            


### FIXED CODE ###

r,g,b,n = map(int,input().split())

ans = 0
for i in range(n+1):
    x = n - r * i
    for j in range(x+1):
        y = x - g * j
        if y >= 0 and y % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
l = []
i = 0
for x in input().split():
    A = int(x)
    if K < N - i:
        l.append(A)
    if i >= K:
        if l.pop(0) < A:
            print("Yes")
        else:
            print("No")
    i = i + 1


### FIXED CODE ###

N, K = map(int, input().split())
l = []
i = 0
for x in input().split():
    A = int(x)
    if K < N - i:
        l.insert(0, A)
    if i >= K:
        if l.pop() < A:
            print("Yes")
        else:
            print("No")
    i = i + 1
### BUGGY CODE ###

N, K = map(int, input().split())
a = []
b = []
hairetu = []
for i in range(N):
    A, B = map(int, input().split())
    h = [A for i in range(B)]
    hairetu.extend(h)

hairetu.sort()
print(hairetu[K-1])


### FIXED CODE ###

N, K = map(int, input().split())
a = []
b = []
hairetu = []
for i in range(N):
    A, B = map(int, input().split())
    hairetu.append([A, B])

hairetu.sort()
for i in range(N):
    K -= hairetu[i][1]
    if K <= 0:
        print(hairetu[i][0])
        break
### BUGGY CODE ###

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

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card, count in sorted(new_cards.items(), reverse=True):
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()

print(sum(A))


### FIXED CODE ###

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

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card, count in sorted(new_cards.items(), reverse=True):
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()
        else:
            print(sum(A))
            exit()

print(sum(A))
### BUGGY CODE ###

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

a=0

for s in range(y//10000+1)[::-1]:
    for t in range((y-10000*s)//5000+1)[::-1]:
        for u in range((y-10000*s-5000*t)//1000+1)[::-1]:
            if 10000*s+5000*t+1000*u==y and s+t+u==n:
                print(s,t,u)
                a=1
                break
                
            else:
                continue
            break
            
        else:
            continue
        break
        
    else:
        continue
    break
    
if a==0:
    print(-1,-1,-1)

### FIXED CODE ###

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

ans=0

for i in range(y//10000,-1,-1):

    nokori=(y-i*10000)

    for j in range(min(n-i,nokori//5000),-1,-1):
 
        nokori2=nokori-j*5000
    
        if 10000*i+5000*j+1000*(n-i-j)==y:
            print(i,j,n-i-j)
            ans=1
            break
            
    else:
        continue
    break
    
          
if ans==0:
    print(-1,-1,-1)
### BUGGY CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = dict() #絶対値
    dist = dict()
    for h in range(H):
        grid[h] = dict()
        dist[h] = dict()
        for w in range(W):
            grid[h][w] = 0
            dist[h][w] = set()

    for h in range(H):
        A = [int(a) for a in input().split()]
        for w in range(W):
            grid[h][w] = A[w]
    for h in range(H):
        B = [int(b) for b in input().split()]
        for w in range(W):
            grid[h][w] = abs(grid[h][w] - B[w])
    #print(grid)

    dist[0][0] |= {grid[0][0]}
    for h in range(H):
        for w in range(W):
            for item in dist[h][w]:
                if h < H - 1:
                    n = grid[h+1][w]
                    dist[h+1][w] |= {abs(item + n), abs(item - n)}
                if w < W - 1:
                    n = grid[h][w+1]
                    dist[h][w+1] |= {abs(item + n), abs(item - n)}
    
    ans = 1000000
    for item in dist[H-1][W-1]:
        ans =min(ans, item)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = dict() #絶対値
    zero = 12800
    dist = dict()
    for h in range(H):
        grid[h] = dict()
        dist[h] = dict()
        for w in range(W):
            grid[h][w] = 0
            dist[h][w] = 0

    for h in range(H):
        for x, v in enumerate(map(int, input().split())):
            grid[h][x] = v
    for h in range(H):
        for x, v in enumerate(map(int, input().split())):
            grid[h][x] = abs(grid[h][x] - v)

    dist[0][0] |= 2 ** zero >> grid[0][0]
    dist[0][0] |= 2 ** zero << grid[0][0]

    for h in range(H):
        for w in range(W):
            if h < H - 1:
                n = grid[h+1][w]
                dist[h+1][w] |= dist[h][w] >> n
                dist[h+1][w] |= dist[h][w] << n
            if w < W - 1:
                n = grid[h][w+1]
                dist[h][w+1] |= dist[h][w] >> n
                dist[h][w+1] |= dist[h][w] << n
    
    ans = 100000000
    for i in range(zero*2):
        if dist[H-1][W-1] & 1:
            ans = min(ans, abs(i - zero))
        dist[H-1][W-1] >>= 1

    print(ans)

    return 0

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

MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = 2**(n-1), 0 if n <= 1 else 2**(n-2)
for i, x in enumerate(c):
    cnt += (a + b*i) * x

print(cnt * (2 ** n % MOD) % MOD)


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)
### BUGGY CODE ###

Q = int(input())
query = []
mid = []
for _ in range(Q):
    a = list(map(int, input().split()))
    query.append(a)


for i in range(len(query)):
    if query[i][0] == 1:
        mid.append(query[i][1:])

    else:
        ans = 0
        mid.sort(key=lambda x: x[0])
        minx = int((len(mid)+1)/2)
        for j in mid:
            ans += abs(mid[minx-1][0]-j[0])+j[1]
        print(mid[minx-1][0],ans)

### FIXED CODE ###

from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
Q = int(input())
query = []
sumL, sumR = [], []
ans = 0
for _ in range(Q):
    a = list(map(int, input().split()))
    if a[0]==1:
        ans += a[2]
        if len(sumL)==0 or a[1] <= -sumL[0]:
            heappush(sumL, -a[1])
            ans += -sumL[0] - a[1]
        else:
            heappush(sumR, a[1])
            ans += sumL[0] + a[1]
    
        if len(sumR) > len(sumL):
            ans -= sumR[0] + sumL[0]
            heappush(sumL, -heappop(sumR))
            
        elif len(sumL) - len(sumR) >= 2:
            heappush(sumR, -heappop(sumL))

    else:
        print(-sumL[0],ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], int(str(a)+str(dp[i-need])))

print(dp[-1])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], dp[i-need]*10+a)

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

L, R = list(map(int, input().split()))

x = range(L, R + 1)

minimum = 2018
for i in range(len(x) - 1):
  for j in range(i + 1, len(x)):
    minimum = min(minimum, x[i] * x[j] % 2019)
    if minimum == 0:
      break

print(minimum)

### FIXED CODE ###

L, R = list(map(int, input().split(' ')))
#print(L, R)

min = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod_ij = (i * j) % 2019
        if min > mod_ij:
            min = mod_ij
            if min == 0:
                break
    if min == 0:
        break

print(min)
### BUGGY CODE ###

def getInput():
    return [int(i) for i in input().rstrip().split(' ')]

def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a%b)

N = getInput()[0]
sums = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if i == j:
            n = i
        else:
            n = gcd(max(i, j), min(i,j))

        for k in range(1, N+1):
            if n == k:
                sums += n
            elif n == 1 or k == 1:
                sums += 1
            else:
                sums += gcd(max(n, k), min(n, k))

print(sums)


### FIXED CODE ###

import math
def getInput():
    return [int(i) for i in input().rstrip().split(' ')]


N = getInput()[0]
sums = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        n = math.gcd(i, j)
        for k in range(1, N+1):
            sums += math.gcd(n, k)

print(sums)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
def input() -> str:
    return sys.stdin.readline().rstrip()
mod = 10**9 + 7
@lru_cache(maxsize=None)
def dp(i):
    if i == n - 1:
        return 1
    if i == n - 2:
        return 2 - int(n - 1 in a)
    return dp(i + 1) * int(i + 1 not in a) % mod + dp(i + 2) * int(i + 2 not in a) % mod
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
print(dp(0))

### FIXED CODE ###

import sys
def input():
  return sys.stdin.readline().rstrip()
mod = 10**9 + 7
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
notin = [1] * n
for i in a:
  notin[i] = 0
dp = [0] * n
dp[n - 1] = 1
if n > 1:
	dp[n - 2] = 1 + notin[n - 1]
for i in range(n - 3, -1, -1):
  dp[i] += dp[i + 1] * notin[i + 1] % mod
  dp[i] += dp[i + 2] * notin[i + 2] % mod
  dp[i] %= mod
print(dp[0])
### BUGGY CODE ###

N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b

print(dpt[W])


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    
    dpt = [0] * (W+1)
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            a = dpt[j]
            b = dpt[j-w]+v
            if a > b:
                dpt[j] = a
            else:
                dpt[j] = b
    
    print(dpt[W])

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

X = int(input())


def get_result(X):
    a = 0
    while True:
        a5 = a ** 5
        c = a5 - X
        if c < 0:
            c = -c
            b = 0
            while True:
                b5 = b ** 5
                if b5 == c:
                    return a, -b
                if b5 > c:
                    break
                b += 1
        a += 1


a, b = get_result(X)
print(a, b)

### FIXED CODE ###

X = int(input())


def is_ok(A, B, X):
    return A ** 5 - B ** 5 == X


def spiral():
    i = 1
    p = [0, 0]
    yield p
    while True:
        for j in range(i):
            p[0] += 1
            yield p
        for j in range(i):
            p[1] -= 1
            yield p
        i += 1
        for j in range(i):
            p[0] -= 1
            yield p
        for j in range(i):
            p[1] += 1
            yield p
        i += 1


for a, b in spiral():
    if is_ok(a, b, X):
        print(a, b)
        break
### BUGGY CODE ###

N, K = [int(nk) for nk in input().split()]

ans = 0
# a+b=pK b+c=qK c+a=rK
for p in range(1, ((2*N)//K)+1):#1<=p<=(2*N)//K
  for q in range(1, ((2*N)//K)+1):
    for r in range(1, ((2*N)//K)+1):
      a = (( p-q+r)*K)/2
      b = (( p+q-r)*K)/2
      c = ((-p+q+r)*K)/2
      if b < 1:
        break
      elif b > N:
        continue
      elif a < 1 or c < 1:
        continue
      elif a > N or c > N:
        break
      else:
        if a == int(a) and b == int(b) and c == int(c):
          ans += 1

print(ans)

### FIXED CODE ###

N, K = [int(nk) for nk in input().split()]

if K % 2 == 1:
  print((N//K)**3)
else:
  ans1 = (N//K)**3
  ans2 = ((N-(K//2))//K + 1)**3
  print(ans1 + ans2)
### BUGGY CODE ###

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

for _ in range(M):
    A.sort(reverse=True)
    A[0] //= 2

print(sum(A))


### FIXED CODE ###

import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

N, M = map(int, input().split())
A = []
for i in input().split():
    heappush(A, -1 * int(i))
# print(A)

for _ in range(M):
    val = heappop(A)
    if val == 0:
        break
    heappush(A, (val+1)//2)

print(-1 * sum(A))
### BUGGY CODE ###

S = list('S'+input())
#print(S)

cnt = 0
i = 2
while i < len(S):
    if S[i-2] == 'A' and S[i-1] == 'B' and  S[i] == 'C':
        cnt += 1
        S[i-2] = 'B'
        S[i-1] = 'C'
        S[i] = 'A'
        i -= 3
    else:
        i += 1
print(cnt)

### FIXED CODE ###

import re

S = 'S' + input()
new_s = list(S.replace('BC', 'D'))


cnt = 0
A = 0
for i in range(len(new_s)):
    if new_s[i] == 'A':
        A += 1
    elif new_s[i] == 'D':
        cnt += A
    else:
        A = 0
print(cnt)
### BUGGY CODE ###

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

while True:
    #すべてが偶数か確認
    for i in range(N):
        if A[i] % 2 == 0:
            continue
        elif A[i]%2 == 1:
            break 

    for i in range(N):
        A[i] = A[i]/2
    n += 1


print(n)

### FIXED CODE ###

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

while 1:
    #すべてが偶数か確認
    for i in range(N):
        if A[i] % 2 == 0:
            continue
        else:
            F = 1
    
    if F == 1 : break 

    for i in range(N):
        A[i] = A[i]/2
    n += 1


print(n)
### BUGGY CODE ###

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

while True:
  if K == 1:
    answer = 0
    break
  if N <= abs(N - K):
    answer = N
    break
  else:
    N = abs(N - K)

print(answer)
    

### FIXED CODE ###

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

if N % K == 0:
  answer = 0
else:
  if abs(N % K - K) >= N % K:
    answer = N % K
  else:
    answer = abs(N % K - K)

  
print(answer)