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

#頂点を見た時に，枝分かれの本数に応じてansを更新

import math

mod=10**9+7

def permu(a,b):
    c=1
    for i in range(b):
        c*=(a-i)
    return c

N,K=map(int,input().split())
adj=[[] for _ in range(N)]
dep=[0]*N

for i in range(N-1):
    a,b=map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

#各深さにノードが何個あるか
q=[]
q.append([0,-1,0])#node,parent,depth
dep[0]+=1

ans=1
while q!=[]:
    v,p,d=q.pop()
    K2=max(K-2,K-d-1)
    l=len(adj[v])
    P=permu(K2,max(l-d,l-1))    
    ans*=P
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        if next_v!=p:
            q.append([next_v,v,d+1])
            dep[d+1]+=1

print((ans*K)%mod)

### FIXED CODE ###

#頂点を見た時に，枝分かれの本数に応じてansを更新
#permutationのリストを先に作っておく

import sys
input = sys.stdin.readline

mod=10**9+7


N,K=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(N - 1)]
adj=[[] for _ in range(N)]

for a,b in ab:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
    
#順列(K-2)Piを先に
P=[1]
for i in range(N):
    P.append((P[-1]*(K-2-i))%mod)
    

q=[(0,-1,0)]#node,parent,depth

ans=1
while q!=[]:
    v,p,d=q.pop()
    #深さ0or1で塗ることができる色数は異なる
    l=len(adj[v])
    if d==0:
        ans*=(K-1)
    ans*=(P[l-1])
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        #葉は追加しない
        if next_v!=p and len(adj[next_v])!=1:
            q.append((next_v,v,d+1))
if N==1:
    ans=1
print((ans*K)%mod)
### BUGGY CODE ###

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

count = [2]*x
ans = []

for i in range(2**x):
    for j in range(x):
        if ((i>>j)&1):
            count[j]=4
    if sum(count) == y:
        ans = 'Yes'
        break
    else:
        ans = 'No'

print(ans)

### FIXED CODE ###

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

for i in range(x+1):
    foot = 2*i + 4* (x-i)
    if foot == y:
        print('Yes')
        exit()
print('No')
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N//R+1):
	for g in range(N+1):
		b = (N - R * r - G * g) / B
		if b.is_integer() and b >= 0:
			cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N//R+1):
	for g in range((N-R*r)//G+1):
		if (N - R * r - G * g) % B == 0:
			cnt += 1
print(cnt)
### BUGGY CODE ###

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

movable = [0]*N
for i in range(N-1):
    j = i
    while j < N-1 and H[j] >= H[j+1]:
        movable[i] += 1
        j += 1

print(max(movable))


### FIXED CODE ###

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

movable = [0]*N
i = 0
while i < N-1:
    j = i
    while j < N-1 and H[j] >= H[j+1]:
        movable[i] += 1
        j += 1
    i = i + movable[i] + 1

print(max(movable))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
S = list(input())

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d==1:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
        else:
            d = 1
            cnt_l += 1
    else:
        if pre_d==1:
            d = 1
            cnt_l += 1
        else:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
    pre_s = s
    pre_d = d

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

#encoding utf-8

import numpy as np

N, M, Q = map(int, input().split())

L = []
R = []
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

p = []
q = []

for i in range(Q):
    pa, qa = map(int, input().split())
    p.append(pa)
    q.append(qa)

MAP = np.zeros((N, N))
for i in range(M):
    MAP[L[i]-1][R[i]-1] += 1

C = np.zeros((N, N))
C[0][0] = MAP[0][0]
for i in range(N):
    count = 0
    for j in range(N):
        count += MAP[i][j]
        C[i][j] = count
# 
# print(MAP)
# print(C)

for i in range(Q):
    count = 0
    for j in range(q[i]-p[i]+1):
        if j == 0:
            count += C[p[i]-1+j][q[i]-1]
        else:
            count += C[p[i]-1+j][q[i]-1]-C[p[i]-1+j][p[i]-1]
    print(int(count))


### FIXED CODE ###


N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)
 
query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)
 
f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]
 
for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1
 
for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1
 
for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])
### BUGGY CODE ###

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

M = 10 ** 15
DP = [[0] * N for _ in range(N)]

if N % 2 == 0:
  t = -1
else:
  t = 1
for i in range(N):
  DP[0][i] = a[i] * t
t *= -1

for i in range(1, N):
  for j in range(N - i):
    if t > 0:
      DP[i][j] = max(DP[i - 1][j] + a[i + j], DP[i - 1][j + 1] + a[j])
    else:
      DP[i][j] = min(DP[i - 1][j] - a[i + j], DP[i - 1][j + 1] - a[j])
  t *= -1

print(DP[-1][0])

### FIXED CODE ###

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

M = 10 ** 15
DP = [[0] * N for _ in range(N)]

if N % 2 == 0:
  t = -1
else:
  t = 1
for i in range(N):
  DP[0][i] = a[i] * t
t *= -1

for i in range(1, N):
  for j in range(N - i):
    if t > 0:
      DP[i][j] = max(DP[i - 1][j] + a[i + j], DP[i - 1][j + 1] + a[j])
    else:
      DP[i][j] = min(DP[i - 1][j] - a[i + j], DP[i - 1][j + 1] - a[j])
  t *= -1

print(DP[-1][0])
### BUGGY CODE ###

n, m = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()

for _ in range(m):
    b, c = map(int, input().split())
    i = 0
    while A[i] < c:
        A[i] = c
        if i == b-1:
            break
        else:
            i += 1
    A.sort()
            
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()

BC = []
for _ in range(m):
    b, c = map(int, input().split())
    BC.append([b, c])

BC.sort(key=lambda x : x[1], reverse=True)
D = []
i = 0
count = 0
while (len(D) < n) and (len(BC) > i) :
    D.append(BC[i][1])
    count += 1
    if count == BC[i][0]:
        count = 0
        i += 1
        
j = 0
while (len(D) > j) and (A[j] <= D[j]) :
    A[j] = D[j]
    j += 1
    
print(sum(A))
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    flag = 1
    ctn = 0
    for _ in range(q):
        query = input().split()
        if flag:
            if query[0] == "1":
                flag = 0
                ctn += 1
            else:
                if query[1] == "1":
                    s = query[2] + s
                elif query[1] == "2":
                    s = s + query[2]
        else:
            if query[0] == "1":
                flag = 1
                ctn += 1
            else:
                if query[1] == "1":
                    s = s + query[2]
                elif query[1] == "2":
                    s = query[2] + s

    if ctn % 2 == 1:
        print(s[::-1])
    else:
        print(s)

main()

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

def islice(it, cnt):
    for x in it:
        if cnt:
            yield x
            cnt -= 1
        else:
            return

x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)
e = sorted((ci + di for ci in c for di in islice(d, k)), reverse=True)
print('\n'.join(map(str, islice(e, k))))

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())
d = sorted((ai + bi for ai in a for bi in b), reverse=True)[:k]
e = sorted((ci + di for ci in c for di in d), reverse=True)[:k]
print(*e)
### BUGGY CODE ###

from collections import deque
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)

    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = deque([self.node_list[0]])
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)

            if not stack:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])

### FIXED CODE ###

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

tree_list = [input().split() for _ in range(N-1)]

query_list = [input().split() for _ in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0]*N
linked_node_list = [[] for _ in range(N)]

# 無向グラフのリンク関係を作成（上流への接続も含んでいる）
for a, b in tree_list:
  a, b = int(a)-1, int(b)-1
  linked_node_list[a].append(b) #子の追加
  linked_node_list[b].append(a) #子の追加
  
for index, val in query_list_int:
  val_list[index-1] += val

stack = [0] #ルートノードの値を入れたスタックを生成、巡回するターゲットを格納する
parent = [0] * (N+1) #訪問済みノードを記憶するスタックを格納する

#再帰関数を使うとメモリ制限に引っかかるので、whileで順次実行する
# スタックでLIFOを使う。LIFOになるので、一番若い者をみながら深さ優先探索にできる。
# 親ノードを覚えておいて弾くようにする
# 有向グラフで定義すれば親を弾く処理はいらない

while True:
  #ルートから順に巡回
  v=stack.pop()   # 後ろから要素を取り出す
  for child in linked_node_list[v]:
    if child != parent[v]:
      parent[child] = v # 訪問済みノードを格納
      stack.append(child) #このノードvの接続先ノードをスタックに格納
      val_list[child] += val_list[v] #累積和
  if not stack:
    #スタックがなくなれば巡回終了
    break

print(*val_list)
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
Ss = [str(input()) for _ in range(H)]

directions = [[-1,0],
              [0,-1],
              [1,0],
              [0,1]]

answer = 0
import copy
for i in range(H):
    for j in range(W):
        if Ss[i][j]==".":
            todo = deque([[i,j]])
        else:
            continue
        candidate = 0
        while len(todo) > 0:
            base = todo.pop()
            candidate += 1
            
            for direction in directions:
                checking = copy.deepcopy(base)
                for k in range(max(H,W)):
                    checking = [checking[0]+direction[0],checking[1]+direction[1]]
                    if checking[0] < 0 or checking[0] >= H or checking[1] < 0 or checking[1] >= W:
                        break
                    if Ss[checking[0]][checking[1]] == "#":
                        break
                    candidate += 1
        if candidate > answer:
            answer = candidate
print(answer)

### FIXED CODE ###

from collections import deque

H,W = map(int, input().split())
Ss = [str(input()) for _ in range(H)]

yoko = [[0 for _ in range(W)] for _ in range(H)]
tate = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Ss[i][j] == "#" or yoko[i][j] != 0:
            continue
        else:
            paths = [[i,j]]
            temp = 1
            for k in range(j+1, W):
                if Ss[i][k] == ".":
                    temp+=1
                    paths.append([i,k])
                else:
                    break
            for path in paths:
                yoko[path[0]][path[1]] = temp

for i in range(H):
    for j in range(W):
        if Ss[i][j] == "#" or tate[i][j] != 0:
            continue
        else:
            paths = [[i,j]]
            temp = 1
            for k in range(i+1, H):
                if Ss[k][j] == ".":
                    temp+=1
                    paths.append([k,j])
                else:
                    break
            for path in paths:
                tate[path[0]][path[1]] = temp

answer = 0
for i in range(H):
    for j in range(W):
        if answer < tate[i][j]+yoko[i][j]-1:
            answer = tate[i][j]+yoko[i][j]-1
print(answer)
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())
a=deque(map(int,input().split()))
b=deque(map(int,input().split()))
b_sum=deque()
b_sum.append(b[0])
b_j=b[0]
for j in range(1,m):
    b_j=b_j+b[j]
    b_sum.append(b_j)
b_sum.append(10**10)
b_sum.appendleft(0)
b_sum.appendleft(-1)
ans=0
a.append(0)
a_sum=0
for l in range(n+1):
    timecount=k-a_sum
    a_sum+=a[l]
    if timecount>=0:
        ok=0
        ng=m+2
        while ng-ok>1:
            midlle=(ng+ok)//2
            if b_sum[midlle]<=timecount:
                ok=midlle
            else:
                ng=midlle
        ans=max(l+ng-2,ans)
    else:
        break
print(ans)
    

### FIXED CODE ###

import bisect
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a_sum=[]
b_sum=[]
a_sum.append(0)
b_sum.append(0)
for i in range(n):
    a_sum.append(a_sum[i]+a[i])
for j in range(m):
    b_sum.append(b_sum[j]+b[j])
ans=0
for x in range(n+1):
    timecount=k-a_sum[x]
    if timecount>=0:
        y=bisect.bisect_right(b_sum,k-a_sum[x])-1
        ans=max(x+y,ans)
    else:
        break
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
#n個に分けてあげなきゃいけない
#合計はmにならなきゃいけない。素数のときは1確定？
#10 123のとき12から試す。余りが０だといいけどこの場合は３余るこのときあまりは１〜１１
#結局この問題はmを素因数分解して２数の積で表現したときにn以上の数で表せるかって話なわけよ、
#約数っていうのはその数の二乗を境にペアになっているから小さい方で割れれば商が相方になっているというわけ
#できる限り平均的に分けてあげたほうがいいってことはわかる。
#大きい方から下って見つかって瞬間終わりにするほうが賢いかも
#候補のうち最大の数字は
i = int(m/n)
ans = 1
while i >= 1:
    if m % i == 0:
        if m / i >= n:
            ans = i
            break
    i = i-1
print(ans)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###

import sys
for line in sys.stdin:
    n = int(line.rstrip('\n'))
    primeNumbers = range(1, n+1)
    for i in range(2, n+1):
        if primeNumbers[i-1] > 0:
            j = 2 * i
            while j <= n:
                primeNumbers[j-1] = 0
                j += i
    print sum(1 for primeNumber in primeNumbers if primeNumber > 0) - 1

### FIXED CODE ###

import math
import sys

n = 999999
nums = [1] * (n+1)
nums[:2] = [0,0]
    
cnt = 0
while cnt <= math.sqrt(n):
    flg = nums[cnt]
    if flg == 1:
        k = 2
        while k*cnt <= n:
            nums[k*cnt] = 0
            k += 1
    cnt += 1


for line in sys.stdin:
    n = int(line)
    print sum(nums[:n+1])
### BUGGY CODE ###

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


A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = []
E2 = []
F = []

# A + Bの全列挙 からのソート 

for i in A : 
    for j in B : 
        D.append(i+j)
        
E = sorted(D, reverse = True)

for i in range(K) : 
    if len(E) > K : 
        E2.append(E[i])
    else : 
        E2 = E
        
####

for i in E2 : 
    for j in C : 
        F.append(i+j)
        
G = sorted(F, reverse = True)

for i in range(K) : 
    print(G[i])

### FIXED CODE ###

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

A = sorted(list(map(int, input().split()))[:K])
B = sorted(list(map(int, input().split()))[:K])
C = sorted(list(map(int, input().split()))[:K])

ab = sorted(list(a+b for a in A for b in B), reverse = True)[:K]
abc = sorted(list(ab+c for ab in ab for c in C), reverse = True)[:K]

for i in abc : 
    print(i)
### BUGGY CODE ###

s = input()

ret = 0
while 'ABC' in s :
    s = s.replace('ABC', 'BCA', 1)
    ret += 1

print(ret)

### FIXED CODE ###

s =  list(input())

ret = 0
i = 0
a = 0
bc = 0

while True :
    while i < len(s) and s[i] == 'A' :
        a += 1
        i += 1

    while i < len(s) - 1 and s[i:i+2] == ['B', 'C']  :
        bc += 1
        i += 2

    ret += a * bc

    bc = 0

    if i < len(s) and s[i] != 'A' :
        a = 0
        
    while i < len(s) and s[i] != 'A' :
        i += 1

    if i >= len(s) - 1 :
        break
    

print(ret)
### BUGGY CODE ###

N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1 , N + 1):
    if i in A:
        continue
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])


### FIXED CODE ###

N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
crash = 0
idx = 0
for i in range(M):
    A.append(int(input()))
    if i == 0:
        crash = A[0]
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1 , N + 1):
    if i == crash:
        idx += 1
        if idx < M:
            crash = A[idx]
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])
### BUGGY CODE ###

import sys
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


def dfs(v, depth):
    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]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


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


### 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 ###

n, m = input().split()
N = int(n)
M = int(m)

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

for _ in range(M):
    mx = max(A)
    k = A.index(mx)
    A[k] = mx // 2

print(sum(A))


### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

import numpy as np

n, k, q = map(int, input().split())
a = list(int(input()) for i in range(q))

for i in range(n):
  cnt = a.count(i+1)
  if k - q + cnt > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

import numpy as np

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

score = [k - q]*(n+1)

for i in range(q):
  score[a[i]] += 1

for i in range(1,n+1):
  if score[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###



def comp(ext,list0,dev):
    if list0[int((ext[0]+ext[1])/2)]>dev:
        return ext[0],int((ext[0]+ext[1])/2)
    else:
        return int((ext[0]+ext[1])/2),ext[1]


def bis(a,b,list0,dev):
    ls=[a,b]
    while ls[0]+1<ls[1]:
        ls=comp(ls,list0,dev)
    if list0[ls[0]]==dev:
        return ls[0]-1
    elif list0[ls[1]]==dev:
        return ls[1]-1
    else:
        return ls[0]


n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        if l[a]+l[b]>l[n-1]:
            c=n-1
        elif l[a]+l[b]<l[b+1]:
            c=b
        else:
            c=bis(b+1,n-1,l,l[a]+l[b])
        s=s+c-b
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)