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

from fractions import gcd

k=int(input())
count = 0

for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            if i==j and j==l:
                count += i
            elif i==j:
                x = gcd(i,l)
                count += x*3
            elif j==l:
                x = gcd(i,l)
                count += x*3
            elif l==i:
                x = gcd(i,j)
                count += x*3 
            else:
                x = gcd(i,j)
                x = gcd(x,l)
                count += x*6

print(count)


### FIXED CODE ###

from fractions import gcd

k=int(input())
count = 0

g = {}
for i in range(1,k+1):
    for j in range(i,k+1):
        x = gcd(i,j)
        if i==j:
            y=1
        else:
            y=2
        if x in g:
            g[x] += y
        else:
            g[x] = y
            
for i in g:
    for j in range(1,k+1):
        x = gcd(i,j)
        count += x*g[i]
        
print(count)
### BUGGY CODE ###

import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

S = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

# #優先度付きqueue

kl=dict()
kl[0]=1
# a = [0]
# heapq.heapify(a)  # aを優先度付きキューに

for i in range(0,ls):
    tmp=int(ss[i:ls])%2019
    kl[tmp]=kl.get(tmp,0)+1
#print(a)


ans=0

for k in kl:
    val=kl[k]
    ans+=val*(val-1)//2

print(ans)
# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)

### FIXED CODE ###

import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

ss = input()
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

#ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

# #優先度付きqueue

kl=[0]*2019
kl[0]=1
# a = [0]
# heapq.heapify(a)  # aを優先度付きキューに

tmp=0
t2=1
for s in reversed(ss):
    tmp=(tmp+int(s)*t2)%2019
    kl[tmp]+=1
    t2=t2*10%2019
    #print(tmp)

#print(a)




ans=0
for k in kl:
    ans+=k*(k-1)//2
print(ans)

# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

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

a,b,c,d=map(int,input().split())
count=0
for i in range(a,b+1):
    if i%c and i%d:
        count+=1
print(count)

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())
count=0
x=b-a+1
def cal(x):
    return x//c+x//d-x//(c*d//gcd(c,d))
print(b-a+1-(cal(b)-cal(a-1)))
### BUGGY CODE ###

N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
for _ in range(M):
    tmp = A.index(max(A))
    A[tmp] = A[tmp] // 2
print(str(sum(A)))


### FIXED CODE ###

N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] = A[i] // 2
    if i <= N - 2 and A[i] < A[i + 1] and A[0] < A[i+1]:
        i += 1
    else:
        A.sort(reverse=True)
        i = 0
print(str(sum(A)))
### BUGGY CODE ###

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


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def solve():
    A, B = map(int, input().split())

    ans = 1
    max_n = min(A, B)

    if A == B:
        if is_prime(A):
            print(2)
            exit()

    for n in range(2, max_n):
        if A == 1 or B == 1:
            break

        if A % n == 0 and B % n == 0:
            ans += 1

            while True:
                if A % n == 0 and B % n == 0:
                    A = A // n
                    B = B // n
                else:
                    break

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

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


def factorize(n):
    b = 2
    fct = set()
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct |= set([b])
        b = b + 1
    if n > 1:
        fct |= set([n])
    return fct


def solve():
    A, B = map(int, input().split())
    ap = factorize(A)
    bp = factorize(B)
    ans = 1 + len(ap & bp)
    print(ans)


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

n=int(input())
a=[int(j) for j in input().split()]
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

#最小公倍数
def lcm(x,y):
    return x*y//gcd(x,y)

mod=10**9+7
t=a[0]
for i in a:
    t=lcm(t,i)

ans=0
for i in a:
    ans+=t//i
    ans%=mod
print(ans)

### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)
### BUGGY CODE ###

import math
from collections import Counter

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

def comb2(n):
    return n * (n - 1) // 2

c = Counter(A)
ans = 0
for m in c.values():
    if m >= 2:
        ans +=comb2(m)

for a in A:
    print(ans - A.count(a)+1)


### FIXED CODE ###

import math
from collections import Counter

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

def comb2(n):
    return n * (n - 1) // 2

c = Counter(A)
ans = 0
for m in c.values():
    if m >= 2:
        ans +=comb2(m)

for i in range(N):
    print(ans - c[A[i]] + 1)
### BUGGY CODE ###

class Node:
  def __init__(self):
    self.counter = 0
    self.childs = []
    self.parents = set()
  def add_child(self, node):
    self.childs.append(node)
  def add_parents(self, node):
    self.parents.add(node)

N, Q = [int(i) for i in input().split()]
ndic = {}
for i in range(1, N+1):
  ndic[i] = Node()
  ndic[i].add_child(ndic[i])
for i in range(N-1):
  a, b = [int(i) for i in input().split()]
  ndic[a].add_child(ndic[b])
  ndic[b].add_parents(ndic[a])
  for n in ndic[a].parents:
    n.add_child(ndic[b])  
    ndic[b].add_parents(n)

from collections import defaultdict
adddict = defaultdict(int)
for i in range(Q):
  p, x = [int(i) for i in input().split()]
  adddict[p] += x
for k, v in adddict.items():
  if v > 0:
    for j in ndic[k].childs:
      j.counter += v
ans = ""
for k, v in ndic.items():
  ans += str(v.counter) + " "
print(ans[:-1])

### FIXED CODE ###

n, q = map(int, input().split())
 
tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
 
cnt = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
 
check = [0]*n
 
tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)
 
 
print(" ".join(map(str, cnt)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

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

for i in range(M):
    for j in range(N):
        if S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] + 1
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
        dp[i+1][j+1] %= mod

ans = (dp[M][N] + 1) % mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

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

for i in range(M):
    for j in range(N):
        if S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] + 1
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
        dp[i+1][j+1] %= mod

ans = (dp[M][N] + 1) % mod
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    ans = 0
    for i in range(1, N+1):
        for j in range(i, N+1, i):
            ans += j
    print(ans)
main()

### FIXED CODE ###

N = int(input())
ans = 0
for X in range(1, N+1):
  Y = N // X
  ans += Y * (Y + 1) // 2 * X
print(ans)
### BUGGY CODE ###

N=int(input())

def query(i):
    print(i,flush=True)
    s=input()
    if s=='Vacant': exit()
    return s

root=query(0)

def is_ok(ind):
    """
    indが条件を満たすかどうか．問題ごとに定義
    ex.
    if a[ind] >= key:
        return True
    else:
        return False
    """
    # 左ならTrue
    response=query(ind)
    if ind%2==1 and root==response:
        return True
    else: return False



def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False

bin_search_meguru()

### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

from collections import Counter
from fractions import gcd


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

if N >= 10 ** 3:
    lcm = A[0]

    for a in A:
        lcm = (lcm * a) // gcd(lcm, a)

    ans = 0
    for a in A:
        ans += lcm // a
        ans %= MOD

    print(ans)
else:
    def factorization(n):
        arr = Counter()
        temp = n
        for i in range(2, int(-(-n**0.5 // 1)) + 1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr[i] = cnt

        if temp != 1:
            arr[temp] = 1

        if len(arr.keys()) == 0:
            arr[n] = 1

        return arr

    lcm = factorization(A[0])

    for a in A:
        b = factorization(a)
        lcm = lcm | b

    ans = 0
    L = 1
    for key in list(lcm.keys()):
        L *= key ** lcm[key]

    for a in A:
        ans += L // a
        ans %= MOD

    print(ans)


### FIXED CODE ###

from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

for a in A:
    lcm = (lcm * a) // gcd(lcm, a)

ans = 0
for a in A:
    ans += (lcm % MOD) * pow(a, MOD - 2, MOD)
    ans %= MOD

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

N = int(input())
A = list(map(int,input().split()))
# print('A:',A)

from itertools import product
a=[0,1]  #0:buy  1:sell
Ls = list(product(a, repeat=N))
# print('Ls:',Ls)
out=0
for L in Ls:
    # print('L:',L)
    money=1000
    kabu=0
    for i in range(N):
        if L[i]==0:
            kabu+=money // A[i]
            money=money % A[i]

        else:
            money+=kabu*A[i]
            kabu=0
        # print('money,kabu:',money,kabu)
    out=max(out,money)

print(out)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
# print('A:',A)
money=1000
kabu=0

for i in range(N-1):
    if A[i] < A[i+1]:
        kabu+=money // A[i]
        money=money % A[i]
    elif A[i] > A[i+1]:
        money+=kabu*A[i]
        kabu=0
money+=kabu*A[N-1]  #last

print(money)
### BUGGY CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = II()
S = input()

ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if j < i:
            continue
        for k in range(1, N+1):
            if k < j:
                continue
            if j-i != k-j:
                if S[i-1] != S[j-1] and S[i-1] != S[k-1] and S[k-1] != S[j-1]:
                    ans+=1
print(ans)






### FIXED CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1,N-1):
    k=2*j-i
    if k>=N:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
i=1
while len(a)>=2:
    if i>=len(a):
        i=1
    if a[i] % a[0]==0:
        del a[i]
    else:
        a[i]-=a[0]
        if a[i]<=0:
            del a[i]
    i+=1
    a.sort()

print(a[0])

### FIXED CODE ###


n=int(input())
a=[int(i) for i in input().split()]
c=a[0]
def gcd(x,y):
    while y:
        x,y=y,x%y
    return x

for i in a:
    c=gcd(c,i)
print(c)
### BUGGY CODE ###

# 正解ではない

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))
    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while len(q):
        worp_count, x, y = q.popleft()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            if 0 <= i < H and 0 <= j < W and S[i][j] in ('.', '1'):
                q.appendleft((worp_count, i, j))
                S[i][j] = '0'

        for i, j in ((x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)):
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.append((worp_count + 1, i, j))
                S[i][j] = '1'

    return -1


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

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

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

n, m = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
ab.sort()
salary = 0
salaries = [0]
num = 0
for i in range(m):
    if num < n:
        while ab[num][0] <= i + 1:
            salaries.append(ab[num][1])
            num += 1
            if num == n:
                break
    temp = max(salaries)
    salary += temp
    if temp > 0:
        salaries.remove(temp)
print(salary)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
ab.sort()
ans = 0
num = 0
queue = []
heapq.heapify(queue)
for i in range(1, m + 1):
    if num < n:
        while ab[num][0] <= i:
            heapq.heappush(queue, [-ab[num][1], ab[num][0]])
            num += 1
            if num == n:
                break
    if len(queue):
        temp = heapq.heappop(queue)
        ans += -temp[0]
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
import sys
sys.setrecursionlimit(10**9)

def f(L):
    if A[L[-1]-1] not in L:
        L_next = L + [A[L[-1]-1]]
        return f(L_next)
    else:
      return L
L = [1]
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
S = {1}

def f(L, S):
    last = L[-1]-1
    if A[last] not in S:
        L.append(A[last])
        S |= {A[last]}
        return f(L, S)
    else:
        return L
P = f(L, S)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j

if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])
### BUGGY CODE ###

from sys import stdin
import math
import fractions

n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]

a.sort(reverse=True)

for i in range(m):
    a[0] = int(a[0]/2)
    a.sort(reverse=True)

print(sum(a))

### FIXED CODE ###

from sys import stdin
import math
import fractions
import heapq

n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]

a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

for i in range(m):
    t = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-t//2))

print(-sum(a))
### BUGGY CODE ###

from collections import deque

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

que = deque([(0, [], V, 0, True, True)])  # total, negative items, deque, count, left_flag, right_flag
best = 0
while que:
    t, s, v, n, lf, rf = que.pop()
    if n >= K:
        best = max([best, t + sum(s)])
        continue
    if v:
        if lf:
            if v[0] >= 0:
                best = max([best, t + v[0] + sum(s)])
                que.append((t + v[0], s, v[1:], n + 1, lf, rf))
            else:
                que.append((t, s + [v[0]], v[1:], n + 1, lf, rf))
        if rf and len(v) > 1:
            if v[-1] >= 0:
                best = max([best, t + v[-1] + sum(s)])
                que.append((t + v[-1], s, v[:-1], n + 1, lf, rf))
            else:
                que.append((t, s + [v[-1]], v[:-1], n + 1, lf, rf))
    if s:
        s.sort()
        que.append((t, s[1:], [s[0]] + v, n + 1, False, rf))
        que.append((t, s[1:], v + [s[0]], n + 1, lf, False))
        best = max([best, t + sum(s[1:])])

print(best)

### FIXED CODE ###

from collections import deque

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

best = 0
for a in range(min([K, N]) + 1):
    for b in range(min([K, N]) - a + 1):
        L = V[:a] + V[N - b:]
        Lp = [i for i in L if i >= 0]
        Lm = [i for i in L if i < 0]
        Lm.sort()
        s = sum(Lp + Lm[min([len(Lm), K - a - b]):])
        best = max([best, s])

print(best)
### BUGGY CODE ###

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

  for i in range(n):
    a[i] = [(-1) * a[i], (-1) * a[i], 1]

  import heapq
  heapq.heapify(a)

  for _ in range(k):
    i = heapq.heappop(a)
    i[2] += 1
    i[0] = i[1] / i[2]
    heapq.heappush(a, i)

  from math import ceil
  print(ceil((-1) * heapq.heappop(a)[0]))

main()

### FIXED CODE ###

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

# binary search
left = 1
right = 10 ** 9

while left < right:
    center = (left + right) // 2

    total = 0
    for i in a:
        if i % center == 0:
            i -= 1
        total += i//center
    
    if total > k:
        left = center + 1
    else:
        right = center

print(left)