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

import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    queue = [(0, 0)]
    while queue:
        v, depth = queue.pop()
        val, w = items[v]

        for j in range(MAX + 1):
            if j < w:
                dp[depth + 1][j] = dp[depth][j]
            else:
                dp[depth + 1][j] = max(dp[depth][j], dp[depth][j - w] + val)

        if len(v_to_il[v]) > 0:
            for i, l in v_to_il[v]:
                ans[i] = dp[depth + 1][l]

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


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

import itertools
import bisect

n = int(input())

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

A = sorted(L)

ans = 0

for a,b in itertools.combinations(A,2):
    total = a + b
    l = bisect.bisect(A,max(a,b))
    r = bisect.bisect_left(A,total) 
    ans += max(0,r-l)

print(ans)        

### FIXED CODE ###

import itertools
import bisect

n = int(input())

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

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

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

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

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

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
        
    s[y][x]='#'
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i:
                continue
            if x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)

for _ in range(250):
    for i in nxt:
        if i[0]==dh and i[1]==dw:
            print(i[2])
            exit()
        rcl(i[0],i[1],i[2])
print(-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

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

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)
### BUGGY CODE ###

S = input()
t = ''
for i in range(len(S)):
    if t == '':
        t += S[i]
    elif t[-1] != S[i]:
        t = t[:-1]
    else:
        t += S[i]
print(len(S)-len(t))

### FIXED CODE ###

S = input()
t = []
for s in S:
    if len(t) == 0:
        t += s
    elif t[-1] != s:
        t.pop()
    else:
        t += s
print(len(S)-len(t))
### BUGGY CODE ###

s = input()
t = input()
dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]

for s_i in range(len(s)):
    for t_i in range(len(t)):
        if s[s_i] == t[t_i]:
            dp[s_i+1][t_i+1] = max(dp[s_i][t_i], dp[s_i+1][t_i], key=len) + s[s_i]
        else:
            dp[s_i+1][t_i+1] = max(dp[s_i][t_i], dp[s_i+1][t_i], key=len)

print(dp[len(s)][len(t)])


### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

for s_i in range(len(s)):
    for t_i in range(len(t)):
        if s[s_i] == t[t_i]:
            dp[s_i+1][t_i+1] = dp[s_i][t_i] + 1
        else:
            dp[s_i+1][t_i+1] = max(dp[s_i][t_i+1], dp[s_i+1][t_i])

ans = []
s_i = len(s)
t_i = len(t)
while s_i > 0 and t_i > 0:
    if dp[s_i][t_i] == dp[s_i][t_i-1]:
        t_i -= 1
    elif dp[s_i][t_i] == dp[s_i-1][t_i]:
        s_i -= 1
    else: #dp[s_i][t_i]  dp[s_i-1][t_i] == 1:
        s_i -= 1
        t_i -= 1
        if t_i >= 0:
            ans.append(t[t_i])


print("".join(ans[::-1]))
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
eg = [(p[i]*(p[i]+1)//2)/p[i] for i in range(n)]
maxsum = 0
for i in range(n-k+1):
	cnt = sum(eg[i:i+k])
	if cnt >= maxsum:
		maxsum = cnt
print(maxsum)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
u = sum(p[0:k])
maxsum = u
for i in range(1, n-k+1):
	u = u + p[i+k-1] - p[i-1]
	if u >= maxsum:
		maxsum = u
print((maxsum+k)/2)
### BUGGY CODE ###

a,b,k=map(int, input().split())
for i in range(a,b+1):
	if i<(a+k) or i>(b-k):
		print(i)


### FIXED CODE ###

a,b,k = map(int, input().split())
for i in range(a,min(b+1,a+k)):
    print(i)
for i in range(max(b-k+1,(a+k)),b+1):
    print(i)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
c=[0]*60
for aa in a:
  for i in range(60):
    if aa&(1<<i):c[i]+=1
ans=0
for i,cc in enumerate(c):
  ans+=cc*(n-cc)*2**i
  ans%=mod
print(ans)




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
c=[0]*60
for aa in a:
  for i in range(60):
    if aa&(1<<i):c[i]+=1
ans=0
for i,cc in enumerate(c):
  ans+=cc*(n-cc)*2**i
  ans%=mod
print(ans)
### BUGGY CODE ###

mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*3**q+q*3**(q-1))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)


### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*pow(3, q, mod)+q*pow(3, (q-1), mod)) if q>0 else int(x*pow(3, q, mod))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
s = [0] * k
for i in range(k):
    s[i] = list(map(int, input().split()))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    for lr in s:
        for d in range(lr[0], lr[1]+1):
            if i+d <= n:
                dp[i+d] += dp[i]

print(dp[n] % mod)


### FIXED CODE ###

# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])
### BUGGY CODE ###

N, K = map(int, input().strip().split())
result = 0
for a in range(K, N+1, K):
    for b in range(a, N + 1, K):
        for c in range(b, N + 1, K):
            if a == b and b == c:
                result += 1
            elif a == b or b == c:
                result += 3
            else:
                result += 6

if K % 2 == 1:
    print(result)
else:
    start = K // 2
    for a in range(start, N + 1, K):
        for b in range(a, N + 1, K):
            for c in range(b, N + 1, K):
                if a == b and b == c:
                    result += 1
                elif a == b or b == c:
                    result += 3
                else:
                    result += 6
    print(result)

### FIXED CODE ###

N, K = map(int, input().strip().split())
result = 0
num = N // K
result += num
if num == 2:
    result += num * (num - 1) * 3
elif num > 2:
    result += num * (num - 1) * 3
    result += num * (num - 1) * (num - 2)


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    num = (N - start) // K + 1
    result += num
    if num == 2:
        result += num * (num - 1) * 3
    elif num > 2:
        result += num * (num - 1) * 3
        result += num * (num - 1) * (num - 2)
    print(result)
### BUGGY CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
for i in range(1, n+1):
    cnt = 0
    for x in range(1, int(math.sqrt(i+1))):
        for y in range(1, int(math.sqrt(i+1))):
            d = (x+y)**2 -4*(x*x + y*y + x*y - i)
            if d < 0:
                pass
            else:
                z = (-(x+y)+math.sqrt(d))/2
                if z == int(z) and z >= 1:
                    cnt += 1
    print(cnt)


### FIXED CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
for i in range(1, n+1):
    cnt = 0
    for x in range(1, int(math.sqrt(i+1))):
        for y in range(1, int(math.sqrt(i+1))):
            d = (x+y)**2 -4*(x*x + y*y + x*y - i)
            if d < 0:
                pass
            else:
                z = (-(x+y)+math.sqrt(d))/2
                if z == int(z) and z >= 1:
                    cnt += 1
    print(cnt)
### BUGGY CODE ###

N = int(input())
l = []
for i in range(N):
    l.append(input())
s = set(l)
cd = {}
m = 0
for i in range(len(s)):
    st = s.pop()
    ct = l.count(st)
    cd[st] = ct
    if ct > m:
        m = ct

ans = []

for i in cd:
    if cd[i] == m:
        ans.append(i)

ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())

dic = {}
m = 1
for i in range(N):
    st = input()
    if st not in dic:
        dic[st] = 1
    else:
        dic[st] += 1
        if dic[st] > m:
            m = dic[st]

ans = []
for s in dic:
    if dic[s] == m:
        ans.append(s)
ans.sort()
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    VN = []
    WN = []
    i = 0
    while i < N:
        w, v = map(int, input().split())
        WN.append(w)
        VN.append(v)
        i += 1

    ans = []
    mask = 0
    while mask < 1<<N:
        i = 0
        w = 0
        v = 0
        while i < N:
            if mask & 1<<i:
                w += WN[i]
                v += VN[i]
            i += 1
        if w <= W:
            ans.append(v)
        mask += 1

    print(max(ans))

main()


### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []
    i = 0
    while i < N:
        w, v = map(int, input().split())
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                    if w <= W:
                        ans.append(v)

    print(max(ans))

main()
### BUGGY CODE ###

import math

nu=int(input())
total=0
for p in range(1,nu):
    num=nu-p
    for j in range(1,math.floor(math.sqrt(num))+1):
        if j**2==num:
            total+=1
        elif num%j==0:
            total+=2
print(total)

### FIXED CODE ###

import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a



nu=int(input())
total=0
for p in range(1,nu):
    s=collections.Counter(prime_factorize(p))
    sama=1
    for j in s.values():
        sama=sama*(j+1)
    total+=sama
print(total)
### BUGGY CODE ###

N, K   = map(int, input().split())
L = list(map(int, input().split()))
L.append(0)
L=sorted(L)
dis = []
for i in range(N-K+1):
    if 0 in L[i:i+K+1]:
        l = L[i:i+K+1]
              
        d = abs(l[0]) + abs(l[-1])*2
        dis.append(d)
        d = abs(l[0])*2 + abs(l[-1])
        dis.append(d)
print(min(dis))


### FIXED CODE ###

N, K  = map(int,input().split())
L =list(map(int,input().split()))
Lzero = list(filter(lambda x:x==0,L))
Lright = list(filter(lambda x:x>0,L))
Lleft = list(map(lambda x:abs(x),filter(lambda x:x<0,L)))[::-1]
K -= len(Lzero)
if K <= 0:
    print(0)
    quit()

dis = []
if len(Lright) == 0:
    print(Lleft[K-1])
    quit()
if len(Lleft) == 0:
    print(Lright[K-1])
    quit()
try :
    dis.append(Lright[K-1])
    dis.append(Lleft[K-1])
except:
    pass


for i in range(len(Lright)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lright[i])
        break
    d = 2*Lright[i]
    remain -= (i+1)
    try :
        d += Lleft[remain-1]
        dis.append(d)
    except:
        pass
for i in range(len(Lleft)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lleft[i])
        break
    d = 2*Lleft[i]
    remain -= (i+1)
    try:
        d += Lright[remain-1]
        dis.append(d)
    except:
        pass
print(min(dis))
### BUGGY CODE ###

import fractions
from functools import reduce
N,*a=map(int,open(0).read().split())
L=[]
R=[]
for i in range(N):
    L.append(reduce(fractions.gcd,a[:i+1]))
    R.append(reduce(fractions.gcd,a[(N-1)-i:]))
L.pop()
R.pop()
R.reverse()    
#print(L,R)
LR=[R[0]]
for i in range(1,N-1):
    LR.append(fractions.gcd(L[i-1],R[i]))
LR.append(L[-1])
print(max(LR))

### FIXED CODE ###

import fractions
#from functools import reduce
N,*a=map(int,open(0).read().split())
L=[]
L_base=a[0]
b=a[:]
b.reverse()
R=[]
R_base=b[0]
for i in range(N-1):
    L_base=fractions.gcd(L_base,a[i])
    L.append(L_base)
    R_base=fractions.gcd(R_base,b[i])
    R.append(R_base)
LR=[R[-1]]
for i in range(N-2):
    LR.append(fractions.gcd(L[i],R[-2-i]))
LR.append(L[-1])
print(max(LR))
### BUGGY CODE ###

from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def __len__(self):
        return len(self.hq)

def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    ans = 0
    dhq = Descending_HeapQueue()
    pointer = 0
    for m in range(1, M+1):
        for a, b in AB[pointer:]:
            if a > m:
                break
            dhq.push(b)
            pointer += 1
        if len(dhq) > 0:
            ans += dhq.pop()
    print(ans)
main()

### FIXED CODE ###

from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def __len__(self):
        return len(self.hq)

def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    ans = 0
    dhq = Descending_HeapQueue()
    pointer = 0
    for m in range(1, M+1):
        while (pointer < N) and (AB[pointer][0] <= m):
            dhq.push(AB[pointer][1])
            pointer += 1
        if len(dhq) > 0:
            ans += dhq.pop()
    print(ans)
main()
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

from collections import deque

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

maze = [input() for i in range(h)]

ans = 0
INF = 20 * 20 + 1
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        if maze[by][bx] == "#": continue
                        ct = cnt[y][x] + 1
                        if ct > cnt[by][bx]: continue 
                        q += [(by,bx)] 
                        cnt[by][bx] = ct
                        ans = max(ans, cnt[by][bx])


print(ans)

### FIXED CODE ###

from collections import deque

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

maze = [input() for i in range(h)]

ans = 0
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[0] * w for _ in range(h)] 
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    ny = y + by
                    nx = x + bx
                    if 0 <= ny < h and 0 <= nx < w:
                        if maze[ny][nx] == "." and cnt[ny][nx] == 0:
                            q += [(ny,nx)]
                            cnt[ny][nx] += cnt[y][x] + 1
                            ans = max(ans, cnt[ny][nx])
                if y == j and x == i:
                    cnt[y][x] = -1


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

# coding: utf-8
import itertools

N, K = map(int, input().split())
lst = [int(input()) for _ in range(N)]
lst2 = list(itertools.combinations(lst, K))

lst3 = []
for l in lst2:
    diff = max(l)-min(l)
    lst3.append(diff)

print(min(lst3))

### FIXED CODE ###

# coding: utf-8
import itertools

N, K = map(int, input().split())
lst = sorted([int(input()) for _ in range(N)], reverse=True)

ans = 10000000000
for i in range(N-K+1):
    l = lst[i]-lst[i+K-1]
    if l < ans:
        ans = l
print(ans)
### BUGGY CODE ###

import numpy as np
import sys

input = sys.stdin.readline

N,M = [int(a) for a in input().split()]
A = np.array([int(a) for a in input().split()], dtype=int)

A = np.sort(A)[::-1]

for i in range(M):
    max_idx = np.argmax(A)
    A[max_idx] //= 2

print(sum(A))

### FIXED CODE ###

import sys
import heapq
from math import ceil

input = sys.stdin.readline

N,M = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

hq = []
for i in range(N):
    heapq.heappush(hq, -A[i])

for i in range(M):
    m = heapq.heappop(hq)
    heapq.heappush(hq, ceil(m / 2))

print(-sum(hq))