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

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))


import itertools
val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a in range(len(A_list)):
    if a + 1 > K:
        break
    for b in range(len(B_list)):
        if b + 1 > K:
            break
        if (a+1) * (b+1) > K:
            continue
            
        for c in range(len(C_list)):
            if c + 1 > K:
                break
            if (a+1) * (b+1) * (c+1) > K:
                continue
        
            val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])

    


            


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a in range(len(A_list)):
    if a + 1 > K:
        break
    for b in range(len(B_list)):
        if b + 1 > K:
            break
        if (a+1) * (b+1) > K:
            break
            
        for c in range(len(C_list)):
            if c + 1 > K:
                break
            if (a+1) * (b+1) * (c+1) > K:
                break
        
            val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])
### BUGGY CODE ###

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

ans=1
for i in range(1,N):
  p_prev = sorted(p[0:i])
  if p[i] < p_prev[0]:
    ans += 1
    
print(ans)

### FIXED CODE ###

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

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

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

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

dp = [a[1], a[0], gcd(a[0], a[1])]
for i in range(2, n):
    for j in range(i+1):
        if j != i:
            dp[j] = gcd(a[i], dp[j])
    dp += [gcd(a[i], dp[i])]


print(max(dp))

### FIXED CODE ###

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

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

l = [0 for i in range(n+1)]
r = [0 for i in range(n+1)]

for i in range(1, n+1):
    l[i] = gcd(l[i-1], a[i-1])

for i in range(n)[::-1]:
    r[i] = gcd(r[i+1], a[i])

m = [0 for i in range(n)]

for i in range(n):
    m[i] = gcd(l[i], r[i+1])

print(max(m))
### BUGGY CODE ###

def solve(a):
	b = a.copy()
	b.sort()
	l = len(a)
	idx = map(b.index, a)
	cnt = 0
	for i, k in enumerate(idx):
		cnt += (i-k) % 2
	return cnt // 2

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(a))


### FIXED CODE ###

def solve(a):
	l = len(a)
	h = l//2 + l%2
	a0 = [a[2*i] for i in range(h)]
	b = a.copy()
	b.sort()
	b0 = [b[2*i] for i in range(h)]

	a0 = set(a0)
	b0 = set(b0)

	return len(a0 - b0)
n = int(input())
a = [int(input()) for i in range(n)]
print(solve(a))
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
  k=input().split()
  if k[0]=='2' and k[1]=='1':
    s=k[2]+s
  if k[0]=='2' and k[1]=='2':
    s=s+k[2]
  if k[0]=='1':
    s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
direction=1
#↑で1は右向き2は左向きに対応。
migi_matu=''
hidari_matu=''
#↑リストにしてしまうと後で文字sと連結できなくなる。
for i in range(q):
  k=input().split()
  #k[0] is Ti, k[1] is Fi, k[2] is character
  if k[0]=='1':
    direction*=(-1)
  if k[0]=='2':
    if k[1]=='1':
      if direction==1:
        hidari_matu+=k[2]
      if direction==-1:
        migi_matu+=k[2]
    else:
      if direction==1:
        migi_matu+=k[2]
      if direction==-1:
        hidari_matu+=k[2]
#  print('入力は',k,'とする。このとき')
#  print(i,'回目の操作後')
#  print(direction)
#  if direction==1:
#    print(hidari_matu[::-1]+s+migi_matu)
#  if direction==-1:
#    print(migi_matu[::-1]+s[::-1]+hidari_matu)
  
  
if direction==1:
  print(hidari_matu[::-1]+s+migi_matu)
if direction==-1:
  print(migi_matu[::-1]+s[::-1]+hidari_matu)
### BUGGY CODE ###

import numpy as np

H,N = map(int,input().split())
INF = 10 ** 10
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(N):
  attack,magic = map(int,input().split())
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    target = j + attack
    if j + attack > H:
      target = H
    if dp[target] > dp[j] + magic:
      dp[target] = dp[j] + magic
      
print(dp[-1])

### FIXED CODE ###

H,N = map(int,input().split())
INF = 10 ** 10
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(N):
  attack,magic = map(int,input().split())
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    target = j + attack
    if j + attack > H:
      target = H
    if dp[target] > dp[j] + magic:
      dp[target] = dp[j] + magic
      
print(dp[-1])
### BUGGY CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  h -= ds[i]
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

### FIXED CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
    A[N-1]=A[N-1]//2
    A.sort()
cost=0
for j in range(N):
    cost+=A[j]
print(cost)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=[-1*int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a=-1*heapq.heappop(A)
    a=a//2
    heapq.heappush(A,-1*a)
print(-1*sum(A))
### BUGGY CODE ###

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

ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0

for x in range(K+1):
    for y in range(K+1):
        z = S - (x + y)
        if 0 <= z and z <= K:
            ans += 1

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

from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

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

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        dist[y][x] = cost
        if y==dh and x==dw:
            return dist
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

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

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        if y==dh and x==dw:
            return dist
        if dist[y][x] < cost: continue
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])
### BUGGY CODE ###

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

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

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 10 ** 9 + 7

l = 1
for i in A:
    l = lcm(l,i)
    
ans = 0
for i in range(N):
    ans += l // A[i]
    ans %= mod
    
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


mod = 10 ** 9 + 7

l = 1
ans = 0
for i in A:
    l = (l * i) // gcd(l,i)
    ans += pow(i, mod-2, mod)
    ans %= mod
l %= mod
ans = (l * ans) % mod

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

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    # A = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]

    print(sum(a for a in range(1, N)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    # A = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]

    print((N*(N-1))//2)


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

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

for i in range(len(a)):
    tmp = a.pop(i)
    print(max(a))
    a.insert(i, tmp)



### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

max1 = max(a)
max2 = sorted(a)[-2]

if a.count(max1) >= 2:
    for i in range(n):
        print(max1)
elif a.count(max1) == 1:
    for i in range(n):
        if a[i] == max1:
            print(max2)
        else:
            print(max1)
### BUGGY CODE ###

mondai, kaitou = map(int, input().split())

# 問題ごとの
clearNo = []
# 問題ごとのWrong
wrong = {}
cleard = 0
pena = 0
# 解答数分繰り返す
for i in range(kaitou):
    qNo, kaitou = input().split()
    qNo = qNo
    if qNo in clearNo:
        continue
    else:
        if kaitou == 'WA':
            if qNo in wrong:
                wrong[qNo] += 1
            else:
                wrong[qNo] = 1
        else:
            cleard += 1
            if qNo in wrong:
                pena += wrong[qNo]
            clearNo.append(qNo)

print(str(cleard) + ' ' + str(pena))


### FIXED CODE ###

mondai, kaitou = map(int, input().split())

# 問題ごとのクリア管理
clearNo = [0] * (mondai+1)
# 問題ごとのWrong
wrong = [0] * (mondai+1)
cleard = 0
pena = 0
# 解答数分繰り返す
kaitous = [input().split() for _ in range(kaitou)]
for i in kaitous:
    qNo = int(i[0])
    result = i[1]
    if clearNo[qNo] == 1:
        continue
    else:
        if result == 'WA':
            wrong[qNo] += 1
        else:
            clearNo[qNo] = 1
            cleard += 1
            pena += wrong[qNo]

print(str(cleard) + ' ' + str(pena))
### BUGGY CODE ###

n,m=input().split()
n=int(n)
m=int(m)
li=[int(k) for k in input().split()]
dp=[0]*n
dp[0]=0
dp[1]=abs(li[1]-li[0])
for i in range(2,n):
  ans=10**9
  for j in range(1,m+1):
    if i-j<0:
      break
    ans=min(ans,abs(li[i]-li[i-j])+dp[i-j])
  dp[i]=ans
#print(dp)  
print(dp[n-1])  


### FIXED CODE ###

n,m=input().split()
n=int(n)
m=int(m)
li=[int(k) for k in input().split()]
dp=[0]*n
dp[0]=0
dp[1]=abs(li[1]-li[0])
for i in range(2,n):
  ans=10**9
  for j in range(1,m+1):
    if i-j<0:
      break
    ans=min(ans,abs(li[i]-li[i-j])+dp[i-j])
  dp[i]=ans
#print(dp)  
print(dp[n-1])
### BUGGY CODE ###

import numpy as np


def main():
    MOD = 10**9 + 7
    A_UB = 2**60  # upper bound
    MAX_BIN_LENGTH = len('{:b}'.format(A_UB))

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

    bit = 1
    answer = 0
    for b in range(MAX_BIN_LENGTH):
        a_bits = A & 1
        one_num = sum(a_bits)
        answer += (one_num * (N - one_num) * bit) % MOD
        answer %= MOD
        bit *= 2
        bit %= MOD
        A >>= 1
    print(answer)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np


def main():
    MOD = 10**9 + 7
    A_UB = 2**60  # upper bound
    MAX_BIN_LENGTH = len('{:b}'.format(A_UB))

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

    bit = 1
    answer = 0
    for b in range(MAX_BIN_LENGTH):
        a_bits = A & 1
        one_num = np.count_nonzero(a_bits)
        answer += (one_num * (N - one_num) * bit) % MOD
        answer %= MOD
        bit *= 2
        bit %= MOD
        A >>= 1
    print(answer)


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

N,Q=map(int,input().split())
S=input()
A=[]
B=[]
l=[]

for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        l.append(i)

for i in range(Q):
    a,b=map(int,input().split())
    A.append(a-1)
    B.append(b-1) 
    
for i in range(Q):    
    count=0
    for item in l:    
        if A[i]<=item and (item+1)<=B[i]:
            count+=1
    print(count)


### FIXED CODE ###

import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
S=input()
A=[]
B=[]
l=[0]

for _ in range(Q):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

count=0
for i in range(1,N):
    if S[i-1]=="A" and S[i]=="C":
        count+=1
    l.append(count)

for i in range(Q):
    print(l[B[i]-1]-l[A[i]-1])
### BUGGY CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_sugar = f*e*100/(100+e)
box = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    if water > f:
      break
    sugar_range = math.ceil(max_sugar/c)
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        if sugar > max_sugar:
          break
        amount = water + sugar
        if amount == 0:
          break
        conc = 100*sugar / amount
        if amount <= f and conc <= e*100/(100+e):
          box[conc] = [amount,sugar]
answer = max(box.items(),key = lambda x:x[0])[1]
print(str(answer[0]) + " " +str(answer[1]))

### FIXED CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_nodo = e/(e+100)
answer = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    max_sugar = water*e/100
    sugar_range = int(math.ceil(max_sugar/c))
    if water >= f:
      break
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        total = water + sugar
        nodo = sugar / total
        if total > f:
          break
        if sugar > max_sugar:
          break
        answer[nodo] = [total,sugar]
ans = max(answer.items(),key = lambda x:x[0])[1]

#print(answer)
print(str(ans[0]) + " " + str(ans[1]))
### BUGGY CODE ###

import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N - 1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log2(A_i + 1)) - A_i
        j = bisect.bisect_left(A, comp, 0, i - 1)
        while True:
            if A[j] == comp:
                if used[j] == 0:
                    ans += 1
                    used[j] = 1
                    break
                else:
                    if j + 1 < i:
                        j += 1
                    else:
                        break
            else:
                break

print(ans)


### FIXED CODE ###

import bisect
import math
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += min(num[j], num[i])
                        num[j] = max(num[j] - num[i], 0)
                        break
                    elif num[j] >= 2:
                        add = num[j] // 2
                        ans += add
                        num[j] = num[j] % 2
                        break
                    else:
                        break
                else:
                    break
            else:
                break

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

N,K,Q = [int(i) for i in input().split()]
mem_point = [K for i in range(N)]
for rounds in range(Q):
  anser = int(input())
  for i in range(len(mem_point)):
    if anser == (i+1):
      pass
    else:
      mem_point[i] -= 1
      
for point in mem_point:
  if point > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = [int(i) for i in input().split()]
mem_point = [K-Q for i in range(N)]


for rounds in range(Q):
  temp = int(input())
  mem_point[temp-1] += 1 
  
for point in mem_point:
  if 0 < point:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N = int(input())

results, counts = [], []
for i in range(1, 31):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            result = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            results.append(result)
            if i == j and j == k:
                counts.append(1)
            elif i == j or j == k:
                counts.append(3)
            else:
                counts.append(6)

combined = zip(results, counts)
combined = sorted(combined)


for n in range(1, N + 1):
    total = 0
    for result, count in combined:
        if result > n:
            break
        elif result == n:
            total += count
    print(total)

### FIXED CODE ###

N = int(input())

counts = [0] * 10001
for i in range(1, 101):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            result = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            if result > 10000:
                continue
            if i == j and j == k:
                counts[result] += 1
            elif i == j or j == k:
                counts[result] += 3
            else:
                counts[result] += 6

for n in range(1, N + 1):
    print(counts[n])
### BUGGY CODE ###

import io
import sys
import math
import itertools
N = int(input())
A = list(map(int, input().split()))

Springboard = []
for i in range(1,len(A)):
  # 自分より前に自分より身長が高い人がいないとき
  if max(A[:i+1]) == A[i]:
    Springboard.append(0)
    # 自分より前に自分より身長が高い人がいるとき
  else:
    Springboard.append(max(A[:i]) - A[i])

print(sum(Springboard))

### FIXED CODE ###

# input here
_INPUT = """\
5
3 3 3 3 3
"""

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    Springboard = []
    max = A[0]
    for i in range(1,len(A)):
    # 自分より前に自分より身長が高い人がいないとき
        if max < A[i]:
            max = A[i]
            Springboard.append(0)
     # 自分より前に自分より身長が高い人がいるとき
        else:
            Springboard.append(max - A[i])

    print(sum(Springboard))

if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools

    # sys.stdin = io.StringIO(_INPUT)
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C = []
for _ in range(m):
    b, c = map(int, input().split())
    C.extend([c for _ in range(b)])
C.sort(reverse=True)

for i in range(min(len(C), n)):
    if C[i] <= A[i]:
        break
    A[i] = C[i]

print(sum(A))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

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

dp = [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)

print(dp[W])

### FIXED CODE ###

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

dp = [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        a = dp[j-w]+v
        if dp[j] < a:
            dp[j] = a

print(dp[W])
### BUGGY CODE ###

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

M=max(a)
for i in range(100):
  if 2**i>M:
    x=i
    break
L=[]
for j in range(2**x-1):
  L.append(0)

for j2 in range(n):
  L[a[j2]-1]+=1

for k in range(x,1,-1):
  l1=L[0:2**(k-1)-1]
  l2=L[2**(k-1):2**k]
  l2.reverse()
  ct+=int(L[2**(k-1)-1]/2)
  for m in range(len(l1)):
    if l1[m]>=1 and l2[m]>=1:
      ct+=min(l1[m],l2[m])
      l1[m]-=min(l1[m],l2[m])
      l2[m]-=min(l1[m],l2[m])
  L=l1
ct+=int(L[0]/2)
print(ct)

### FIXED CODE ###

import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[1]*n
for i in range(n-1,-1,-1):
  if a[i]==1:
    break
  if check[i]==1 and a[i] not in b:
    check[i]=0
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    t=bisect.bisect_left(check[y:z],1)+y
    if t!=z:
      check[t]=0
      ct+=1

ctb=0
w=1
for i in range(n):
  if a[i] in b or a[i]==1:
    if a[i]==w:
      if check[i]==1:
        ctb+=1
    else:
      ct+=ctb//2
      w=a[i]
      if check[i]==1:
        ctb=1
      else:
        ctb=0
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

print(ct)