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

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (1 << b.bit_length()) - b
        if a == b:
            ans += c[b]//2
            c[b] %= 2
        else:
            if a in c.keys() and c[a] > 0:
                cur = min(c[a], c[b])
                ans += cur
                c[b] -= cur
                c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


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

import bisect
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(int(input()))
cnt = 0
while len(a_ls) > 0:
    cnt += 1
    L_ls = [a_ls[0]]
    for a in a_ls[1:]:
        if L_ls[-1] < a:
            L_ls.append(a)
        else:
            L_ls[bisect.bisect_left(L_ls, a)] = a
    for a in L_ls:
        a_ls.remove(a)
print(cnt)

### FIXED CODE ###

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

#!/usr/bin/env python
# coding: utf-8

# In[19]:


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


# In[20]:


#print(A)
for i in range(M):
    A[A.index(max(A))] = int(max(A) / 2)
    #print(A)
print(sum(A))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[18]:


import heapq


# In[23]:


N,M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))


# In[24]:


heapq.heapify(A)
for m in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, -(-tmp//2))
print(-sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
M = 1000000007
n = int(input())
tmp = list(map(int, input().split()))
A = [a % M for a in tmp]
ans = 0
for i in range(1,n):
    ans += (A[i-1] * ((sum(A[i::])%M)))%M
print(ans%M)

### FIXED CODE ###

import sys
input = sys.stdin.readline
M = 1000000007
n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
for i in range(n):
    s += A[i]
    s %= M

for i in range(n):
    s = s - A[i]
    if s < 0:
        s += M
    ans += A[i] * s
    ans %= M
print(ans)
### BUGGY CODE ###

#import copy
import sys
 
H, W = map(int, input().split())
#dist_matrix = [[10000] * W for i in range(H)]
black_h_list = []
black_w_list = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      black_h_list.append(i)
      black_w_list.append(j)
 
#print(black_h_list)
#print(black_w_list)

if len(black_h_list) == H*W:
  print(0)
  sys.exit()
  
max_value = 1
for i in range(H):
  for j in range(W):
    min_dist = H+W+2
    if j > 0:
      min_dist = last_dist+1
      
    for k in range(len(black_h_list)):
      if i-black_h_list[k] >= min_dist:
        continue
      elif black_h_list[k]-i >= min_dist:
        break      
      if j-black_w_list[k] >= min_dist:
        continue
      elif black_w_list[k]-j >= min_dist:
        continue
      
      dist = abs(i-black_h_list[k]) + abs(j-black_w_list[k])
      if max_value >= dist:
        min_dist = dist
        break
      elif min_dist > dist:
        min_dist = dist        
    #dist_matrix[i][j] = min_dist
    if max_value < min_dist:
      max_value = min_dist
      
    last_dist = min_dist
    #print(str(i) + "," + str(j) + "," + str(min_dist))

#print(dist_matrix)
    
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

if __name__ == '__main__':

	#入力
	N, K  = map(int,input().split())
	lst = []
	for i in range(0,N):
		a, b = map(int,input().split())
		lst.append([a,b])

	ans_lst = []
	for i in range(0,N):
		a = lst[i][0]
		b = lst[i][1]
		for j in range(0,b):
			ans_lst.append(a)

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

### FIXED CODE ###

if __name__ == '__main__':

	#入力
	N, K  = map(int,input().split())
	lst = []
	for i in range(0,N):
		a, b = map(int,input().split())
		lst.append([a,b])

	lst.sort()
	indx = 0

	for i in range(0,N):
		indx += lst[i][1]
		if indx >= K:
			ans = lst[i][0]
			break

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

N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if j > 0:
            r[i][j] = r[i][j-1] + p[i][j]
        else:
            r[i][j] = p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

### FIXED CODE ###

N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)
### BUGGY CODE ###

N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    for w in range(W+1):
        if  w - WV[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(max(max(dp)))


### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()
### BUGGY CODE ###

input()
da = list(map(int,input().split()))
al = 0
for i in range(len(da)):
  for j in range(len(da)-i):
    if sum(da[i:j+i+1]) == 0:
      al += 1

print(al)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = [int(i) for i in input().split()]
 
s = 0
d = defaultdict(int)
ans = 0
d[0] = 1
 
for i in a:
    s += i
    ans += d[s]
    d[s] += 1
 
print(ans)
### BUGGY CODE ###

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

max_average = 0
point = 0
for i in range(len(P)-K+1):

    if max_average < sum(P[i:i+K]):
        max_average = sum(P[i:i+K])
        point = i

count = 0
for p in range(point, point+K):
    count += sum(range(1, P[p]+1)) / P[p]

print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    tmp_max = sum(P[:K])
    tmp = sum(P[:K])
    for i in range(N-K):
        tmp += P[i+K]
        tmp -= P[i]

        if tmp > tmp_max:
            tmp_max = tmp

    print((tmp_max + K) / 2)

main()
### BUGGY CODE ###

from fractions import Fraction
N , K=map(int, input().split())

F = []

for i in range(1,N + 1):
    point = i
    j = 0
    while True:
        if point >= K:
            break

        point *=  2
        j += 1
    F.append(Fraction(1, N) * (Fraction(1,2) ** j))

print(float(sum(F)))


### FIXED CODE ###

from fractions import Fraction
N, K = map(int, input().split())
F = 0

for i in range(1, N + 1):
    point = i
    j = 0
    while point < K:
        point *= 2
        j += 1
    F += float((1/N) * ((1/2) ** j))

print(F)
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
cnt = 0
start = 0
for i in range(start,N):
    ans = max(ans,cnt)
    cnt = 0
    for j in range(N-i-1):
        if H[i+j] >= H[i+j+1]:
            cnt += 1
        else:
          start = j+1
          break    
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
cnt = 0
for i in range(N-1):
      if H[i] >= H[i+1]:
          cnt += 1
      else:
          ans = max(ans,cnt)
          cnt = 0
      if i+2 == N:
        print(max(ans,cnt))
        exit()
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    S = input()
    N = len(S)
    ans = 0
    for i in range(N):
        for j in range(i+4, N+1):
            if int(S[i:j])%2019 == 0:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    S = input()
    N = len(S)
    memo = [0] * 2019
    now = 0
    ten = [0] * 200100
    ten[0] = 1
    for j in range(len(ten)-50):
        ten[j+1] = ten[j]*10%2019

    for i in range(N):
        now += int(S[-(i+1)])*ten[i]
        now %= 2019
        memo[now] += 1
    
    ans = 0
    for k in range(2019):
        ans += (memo[k] * (memo[k]-1)) // 2

    ans += memo[0]
    #m = collections.Counter(memo)
    #print(m)   
    print(ans)


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

n,k=map(int,input().split())
sushi=[]
for i in range(n):
    sushi.append([])
for i in range(n):
    t,d=map(int,input().split())
    sushi[t-1].append(d)
Max=[]
Rest=[]
for i in sushi:
    if not i==[]:
        Max.append(max(i))
        i.remove(max(i))
        Rest=Rest+i
Max.sort(reverse=True)
Rest.sort(reverse=True)
v=len(Max)
Max_s=[]
Rest_s=[0]
Sum=0
for i in Max:
    Sum=Sum+i
    Max_s.append(Sum)
Sum=0
for i in Rest:
    Sum=Sum+i
    Rest_s.append(Sum)
ans=0
l_r=len(Rest)
for i in range(1,min(k,v)+1):
    if k-i<=l_r:
        temp=Max_s[i-1]+Rest_s[k-i]+i**2
        if ans<temp:
            ans=temp
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
sushi=[]
for i in range(n):
    sushi.append([])
for i in range(n):
    t,d=map(int,input().split())
    sushi[t-1].append(d)
Max=[]
Rest=[]
v=0
for i in sushi:
    if not i==[]:
        Max.append(max(i))
        i.remove(max(i))
        for j in i:
            Rest.append(j)
        v=v+1
Max.sort(reverse=True)
Rest.sort(reverse=True)
Max_s=[]
Rest_s=[0]
Sum=0
for i in Max:
    Sum=Sum+i
    Max_s.append(Sum)
Sum=0
l_r=0
for i in Rest:
    Sum=Sum+i
    Rest_s.append(Sum)
    l_r=l_r+1
ans=0
for i in range(1,min(k,v)+1):
    if k-i<=l_r:
        temp=Max_s[i-1]+Rest_s[k-i]+i**2
        if ans<temp:
            ans=temp
print(ans)
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d: continue
    for (t, c2) in edges[u]:
      cost = 0 if c == c2 else 1
      if d + cost < result[t, c2]:
        result[t, c2] = d + cost
        if cost == 0:
          que.appendleft((d + cost, t, c2))
        else:
          que.append((d + cost, t, c2))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c]:
          result[t, c] = d
          que.appendleft((d, t, c))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int, input().split()))
sm=0
mod=10**9+7
for i in itertools.combinations(A,2):
    sm+=(i[0]*i[1])%mod
    sm%=mod

print(sm)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
sm=0
mod=10**9+7
s=sum(A)
for i in A:
    s-=i
    sm+=i*s
    sm%=mod
print(sm)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
f = [2**i - 1 for i in range(1,N+1) if 2**i - 1 < N + 1 ]
cnt = 0
g = f[::-1]
def insertionSort(a, N, g):
    global cnt
    for i in range(g, N):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
  
m = len(g)    
for j in range(m):
    insertionSort(a, N, g[j])

print(m)
print(" ".join(map(str, g)))
print(cnt)
for i in range(N):
    print(a[i])

### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
f = []
x = 1
while x <= N:
    f.append(x)
    x = 3*x + 1
cnt = 0
g = f[::-1]

def insertionSort(a, N, g):
    global cnt
    for i in range(g, N):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
  
m = len(g)    
for j in range(m):
    insertionSort(a, N, g[j])

print(m)
print(" ".join(map(str, g)))
print(cnt)
for i in range(N):
    print(a[i])
### BUGGY CODE ###

N = int(input())

cnt = 0
for i in range(1, N):
  for j in range(1, N//i + 1):
    if N - i * j >= 1:
      cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())

cnt = 0
for i in range(1, N):
  j =  (N - 1)//i
  cnt += j

print(cnt)
### BUGGY CODE ###

S = input()
n = len(S)
count = 0
T = [0] * (n + 1)
mod_dict = {0:0}

for i in reversed(range(n)):
    #print(i)
    T[i] = T[i+1] + int(S[i]) * (10 ** (n - i - 1))
    # print("Num : " + str(T[i]))
    mod = T[i] % 2019
    # print("Mod : " + str(mod))
    if(mod in mod_dict.keys()):
        mod_dict[mod] = mod_dict[mod] + 1
    else:
        mod_dict[mod] = 0

print(sum(mod_dict.values()))

### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

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

# -*- coding: utf-8 -*-
import fractions
 
tmp=input()
n = int(tmp.split(" ")[0])
X = int(tmp.split(" ")[1])
tmp=input()
i=int(0)
x=[]
for i in range(n):
    x.append(int(tmp.split(" ")[i]))
x.append(X)
x.sort()
y=[]

i=0
while i < n:
    y.append(x[i+1]-x[i])
    i +=1
y.sort()

ya=tuple(set(y))
m=len(ya)
z=y[0]
i=0
while i < m:
    z=fractions.gcd(z,ya[i])
    i+=1

print(z)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
import numpy as np
 
N,X = map(int, input().split())
x = list(map(int,input().split()))
x.append(X)
x.sort()
 
x=np.array(x)
 
y=x[1:]-x[:-1]
 
y.sort()
y=list(set(y))
z=y[0]
m=len(y)
i=0
while i < m:
    z=fractions.gcd(z,y[i])
    i+=1
 
print(z)
### BUGGY CODE ###

import fractions
n = int(input())
a = [int(x) for x in input().split(' ')]
all_m = []
for i in range(n):
    get_a = a[:i] + a[i+1:]
    m = get_a[0]
    for j in range(n-2):
        m = fractions.gcd(m,get_a[j+1])
    all_m.append(m)
print(max(all_m))

### FIXED CODE ###

#125
from fractions import gcd
n = int(input())
a = [int(x) for x in input().split(' ')]

m_r = [0]
for i in range(n-1):
    m_r.append(gcd(m_r[-1], a[i]))

m_l = [0]
for i in range(1, n):
    m_l.append(gcd(m_l[-1], a[-i]))

m = []
for i in range(n):
    m.append(gcd(m_r[i], m_l[-i-1]))
print(max(m))
### BUGGY CODE ###

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

count = 0
for i in range(k+1):
  for j in range(k+1):
    for k in range(k+1):
      tot = i+j+k
      if s == tot:
        count += 1
print(count)

### FIXED CODE ###

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

count = 0
for i in range(k+1):
  for j in range(k+1):
    l = s-i-j
    if l>=0 and l<=k:
      count +=1
print(count)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

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

d=[-1]*N

for i in range(M):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    union(x,y)

LN=[-1]*N
lis=[]
idx=0
for i in range(N):
    if LN[i]==-1:
        temp=members(i)
        l=[]
        for j in temp:
            LN[j]=idx
            l.append(p[j])
        lis.append(l)
        idx+=1

ans=0
for i in range(N):
    for j in lis[LN[i]]:
        if i+1==j:
            ans+=1
            lis[LN[i]].remove(i+1)
            break
print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

def same(a,b):
    if find(a)==find(b):return True
    else:return False

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

d=[-1]*N

for i in range(M):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    union(x,y)

ans=0
for i in range(N):
    if same(i,p[i]-1):
        ans+=1
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()
A = LI()

A.sort()
for i in range(M):
    a_max = A.pop(-1) // 2
    bisect.insort_left(A,a_max)
print(sum(A))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()
A = LI()

pq = []
for a in A:
    heapq.heappush(pq,-a)

for _ in range(M):
    heapq.heappush(pq,-(-heapq.heappop(pq) // 2))
    # print(pq)

print(-sum(pq))