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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:L//3] :
            i += L//3
            continue
        ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9997
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

a=0
for i in range(N-1):
    for k in range(1,N-i-1):
        a=a+sum(x<L[i]+L[i+k] for x in L[i+k+1:N])

print(a)

### FIXED CODE ###

import bisect

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

L=sorted(L)

ans=0
for i in range(N-1):
    for k in range(i+1,N-1):
        a=L[i]+L[k]
        b=bisect.bisect_left(L,a)
        ans=ans+(b-k-1)

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

S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
    if C == "A":
        a += p
    if C == "B":
        b += a
    if C == "C":
        c += b
    a %= mod
    b %= mod
    c %= mod
print(c)


### FIXED CODE ###

S = input()
a = 0
b = 0
c = 0
p = 1
mod = 1000000000+7
for C in S:
    if C == "?":
        c = 3*c+b
        b = 3*b+a
        a = 3*a+p
        p *= 3
    elif C == "A":
        a += p
    elif C == "B":
        b += a
    elif C == "C":
        c += b
    a %= mod
    b %= mod
    c %= mod
    p %= mod
print(c)
### BUGGY CODE ###

from collections import defaultdict

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

cnt = [0]*(N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

root_id = 1
open_list = [root_id]
closed_list = []
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    closed_list.append(cur_id)
    adj_id_list = edge[cur_id]
    for adj_id in adj_id_list:
        if adj_id in closed_list:
            continue
        cnt[adj_id]+=cnt[cur_id]
        open_list.append(adj_id)
print(*cnt[1:])

### FIXED CODE ###

from collections import defaultdict

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

cnt = [0]*(N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

root_node = (1, -1) # (id, value, parent_id)
open_list = [root_node]
closed_list = []
while True:
    if len(open_list) == 0:
        break
    cur_node = open_list.pop()
    cur_id, parent_id = cur_node
    if not(parent_id == -1):
        cnt[cur_id] += cnt[parent_id]
    for child_id in edge[cur_id]:
        if child_id == parent_id:
            continue
        open_list.append((child_id, cur_id))
print(*cnt[1:])
### BUGGY CODE ###

#!/usr/bin/env python3
N, X, Y = [int(str) for str in input().strip().split()]

INF = 100000
d = [[INF] * N for _ in range(N)]

for i in range(N - 1):
    d[i][i + 1] = 1
    d[i + 1][i] = 1
d[X - 1][Y - 1] = 1
d[Y - 1][X - 1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

dists = dict()
for i in range(N):
    for j in range(i + 1, N):
        k = d[i][j]
        dists[k] = dists.get(k, 0) + 1

for k in range(1, N):
    print(dists.get(k, 0))

### FIXED CODE ###

#!/usr/bin/env python3
N, X, Y = [int(str) for str in input().strip().split()]

X -= 1
Y -= 1
dists = [0] * N
for i in range(N - 1):
    for j in range(i + 1, N):
        d = min(j - i, abs(X - i) + abs(Y - j) + 1)
        dists[d] += 1

for k in range(1, N):
    print(dists[k])
### BUGGY CODE ###

# ABC136 C - Build Stairs

n = int(input())
h = list(map(int,input().split()))
for i in range(len(h)):
    for j in range(i+1,len(h)):
        if h[i] - h[j] >= 2:
            print('No')
            exit()
print('Yes')

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
base=0
for h in H:
    if base>h:
        print("No")
        break
    base=max(base,h-1)
else:
    print("Yes")
### BUGGY CODE ###

import itertools

N, X, Y = map(int, input().split())

combi = list(itertools.combinations(range(1,N+1), 2))
dist = [[i+1, 0] for i in range(0, N-1)]

c = [min([kyori[1] - kyori[0], int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))]) for kyori in combi]

for i in range(len(c)):
    dist[c[i]-1][1] += 1
for i in range(0, N-1):
    print(dist[i][1])


### FIXED CODE ###

import itertools

N, X, Y = map(int, input().split())

combi = list(itertools.combinations(range(1,N+1), 2))
dist = [[i+1, 0] for i in range(0, N-1)]

c = [min([kyori[1] - kyori[0], int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))]) for kyori in combi]

for i in range(len(c)):
    dist[c[i]-1][1] += 1
for i in range(0, N-1):
    print(dist[i][1])
### BUGGY CODE ###

x, y = [int(i) for i in input().split()]

if x < y:
    a = x
    x = y
    y = a
if x == y :
    kouyakusu = x

i = 0
while i < int(x%y):
    if (x%y)% (((x%y))-i) == 0 and y%(((x%y))-i) == 0:
        kouyakusu = int((x%y) - i)
        break
    i = i + 1

print(kouyakusu)

### FIXED CODE ###

x, y = [int(i) for i in input().split()]

if x < y:
    a = x
    x = y
    y = a

def kouyakusu(x,y):
    yakusu = x % y
    if yakusu == 0:
        print(y)
        return y
    else:
        kouyakusu(y,yakusu)

max_kouyakusu = kouyakusu(x,y)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

def solve(n):
    if dp[n] is not None:
        return dp[n]

    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        ans = 10**9
        for i in range(1, K + 1):
            if n - i < 0:
                break
            cost = solve(n - i) + abs(h[n - i] - h[n])
            ans = min(ans, cost)
        dp[n] = ans

    return dp[n]

print(solve(N-1))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
### BUGGY CODE ###

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

import math
from functools import reduce

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

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

prime = sieve_of_eratosthenes(2*(10**5)+1)

for p in prime:
  cnt = 0
  for a in A:
    if a%p == 0: cnt += 1
    if cnt == 2:
      if gcd_list(A) == 1: print('setwise coprime')
      else: print('not coprime')
      exit()
print('pairwise coprime')



### FIXED CODE ###

import math
from functools import reduce

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

N=int(input())
A=list(map(int,input().split()))
mA = max(A)
D = [-1]*(mA+1)
D[0]=1
D[1]=1
for i in range(2,mA+1):
  if D[i] != -1: continue
  D[i] = i
  cnt = 2*i
  while cnt < mA+1:
    if D[cnt] == -1:
      D[cnt]=i
    cnt += i
done = set()
for a in A:
  tmp = set()
  while a > 1:
    tmp.add(D[a])
    a //= D[a]
  if len(done&tmp) > 0:
    if gcd_list(A) == 1: print('setwise coprime')
    else: print('not coprime')
    exit()
  done |= tmp
print('pairwise coprime')
### BUGGY CODE ###

n,m=map(int,input().split())
l=["p"]
i=0
while len(l)<m:
  i+=1
  l=["b"]+l+["p"]+l+["b"]
for j in range(n-i):
  l=["b"]+l
c=0
for i in range(m):
  if l[i]=="p":
    c+=1
print(c)


### FIXED CODE ###

n,x=map(int,input().split())
plist=[1]
blist=[1]
for i in range(n):
  plist.append(plist[-1]*2+1)
  blist.append(blist[-1]*2+3)
def patty(n,x):
  if n==0:
    return 1
  else:
    if x==1:
      return 0
    elif 1<x and x<=blist[n-1]+1:
      return patty(n-1,x-1)
    elif x==blist[n-1]+2:
      return plist[n-1]+1
    elif 2+blist[n-1]<x and 2*blist[n-1]+2>=x:
      return plist[n-1]+patty(n-1,x-2-blist[n-1])+1
    else:
      return plist[n]
print(patty(n,x))
### BUGGY CODE ###

l=input()
dp=[3**i for i in range(len(l)+1)]
ans=dp[-1]
t=0
for i,j in enumerate(l,1):
    if(j=="0"):
        ans-=dp[-i-1]*(2**(t+1))
    else:
        t+=1
print(ans%(10**9+7))

### FIXED CODE ###

l=input()
a=len(l)
mod=10**9+7
ans=3**a%mod
t=0
for i,j in enumerate(l,1):
    if(j=="0"):
        ans-=pow(3,a-i,mod)*pow(2,t+1,mod)
    else:
        t+=1
print(ans%(10**9+7))
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a)
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for i in range(1,len(B) + 1):
			C = list(itertools.combinations(B,i))
			for c in C:
				if sum(c) in fusoku:
					need.append(a)
					z = 1
					break
			if z == 1:
				break

print(N - len(need))


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
### BUGGY CODE ###

from collections import Counter
import re


def resolve():
    n = int(input())
    s = input()
    for i in range(n // 2, 0, -1):
        c = Counter([s[x: x + i] for x in range(n - i + 1)])
        for j in c.most_common():
            if j[1] < 2:
                break
            if re.match(r"^.*" + j[0] + r".*" + j[0] + r".*$", s):
                print(i)
                return
    print(0)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def resolve():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n):
        a = z_algo(s[i:])
        for index, j in enumerate(a):
            if j <= index:
                ans = max(ans, j)
    print(ans)


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

N,K,Q = (int(x) for x in input().split())
#参加者全員分の残りポイントが入ったリスト[3,3,3,3,3,3]を作る
point = []
for i in range(N):
    point.append(K)
#正解者の入力に応じてpointを減らしていく[3,3,3,3,3,3]→[2,2,3,2,2,2]
for i in range(Q):
    currect_person = int(input())
    for j in range(N):
        if j != currect_person-1:
            point[j] -= 1
    #print(point)

for i in range(N):
    if point[i] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N,K,Q = (int(x) for x in input().split())
#参加者全員分の残りポイントが入ったリスト[3,3,3,3,3,3]を作る
point = []
for i in range(N):
    point.append(K)
#N人のポイントをはじめに全員分-Qしておく
for i in range(N):
    point[i] -= Q
#正解者ごとに+1する
for i in range(Q):
    point[int(input())-1] += 1
#結果を出力
for i in range(N):
    if point[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

s = input()
t = input()

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

for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
    if s[i-1] == t[j-1]:
      dp[j][i] = max(dp[j][i-1], dp[j-1][i], dp[j-1][i-1] + 1)
    else:
      dp[j][i] = max(dp[j][i-1], dp[j-1][i], dp[j-1][i-1])


ans = ""
x = len(s)
y = len(t)
d = dp[-1][-1]
while True:
  if d == 0:
    break
  if dp[y - 1][x] == d:
    y -= 1
  elif dp[y][x - 1] == d:
    x -= 1
  else:
    ans += t[y - 1]
    x -= 1
    y -= 1
    d -= 1
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()

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

for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
    if s[i-1] == t[j-1]:
      dp[j][i] = max(dp[j][i-1], dp[j-1][i], dp[j-1][i-1] + 1)
    else:
      dp[j][i] = max(dp[j][i-1], dp[j-1][i], dp[j-1][i-1])

ans = ""
x = len(s)
y = len(t)
d = dp[-1][-1]
while True:
  if d == 0:
    break
  if dp[y - 1][x] == d:
    y -= 1
  elif dp[y][x - 1] == d:
    x -= 1
  else:
    ans += t[y - 1]
    x -= 1
    y -= 1
    d -= 1
print(ans[::-1])
### BUGGY CODE ###

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

for i in range(M):
  A[N-1]=int(A[N-1]/2)
  A.sort()
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A =  [-int(x) for x in input().split()]
A.sort()
for i in range(M):
    rem=A[0]
    heapq.heappush(A,int(rem/2))
    heapq.heappop(A)
    
print(-sum(A))
### BUGGY CODE ###

def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x

K = int(input())
ans = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      ans += gcd(i, gcd(j, k))
print(ans)

### FIXED CODE ###

def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x

K = int(input())
ans = 0
for i in range(1, K+1):
  for j in range(i, K+1):
    for k in range(j, K+1):
      if(i == j and j == k):
        ans += i
      elif(i == j or j == k):
        ans += gcd(i, k) * 3
      else:
        ans += gcd(i, gcd(j, k)) * 6
print(ans)
### BUGGY CODE ###

sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
for i in range(n):
    data.append(tuple(map(int,input().split())))
data.append((gx,gy,0))
for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=max(0,((data[i][0]-data[j][0])**2+(data[i][1]-data[j][1])**2)**0.5-data[i][2]-data[j][2])
        g[i].append((tmp,j))
        g[j].append((tmp,i))

from heapq import heappush, heappop, heapify
dist=[2828427127 for i in range(len(g))]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if dist[v]<c:
        continue
    for i in range(len(g[v])):
        tmp=g[v][i][0]+c
        if tmp<dist[g[v][i][1]]:
            dist[g[v][i][1]]=tmp
            heappush(que,(tmp,g[v][i][1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

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

exp = []
for i in range(N):
    exp.append((p[i]+1)/2)    
sum_list = []
for i in range(N-K+1):
    sum_list.append(sum(exp[i:K+i]))
print(max(sum_list))


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
exp = []
sum_list = []
result_list = []
result = 0
count = 0
tmp = 0
for i in range(N):
    if count < K-1:
        a = (p[i]+1)/2
        exp.append(a)
        tmp += a
    else:
        a = (p[i]+1)/2
        exp.append(a)
        tmp += a
        sum_list.append(tmp)
        tmp -= exp[count-K+1]
    count += 1

print(max(sum_list))
### BUGGY CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    s = input()
    if not s in S:
        S.append(s)
        count += 1
print(count)




### FIXED CODE ###

N = int(input())
S = []

for i in range(N):
    S.append(input())

print(len(set(S)))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
p = 0
for i in range(n):
    for j in range(i):
        if(abs(i-j) == a[i]+a[j]):
            p += 1
print(p)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = 0
z = 1000
p = []*z
m = []*z
for i in range(z):
    p.append([])
    m.append([])
for i in range(n):
    x = i+1-a[i]
    if(x > 0):
        if(x in p[x%z]):
            m[x%z][p[x%z].index(x)][0] += 1
        else:
            m[x%z].append([1,0])
            p[x%z].append(x)
    x = i+1+a[i]
    if(x in p[x%z]):
        m[x%z][p[x%z].index(x)][1] += 1
    else:
        m[x%z].append([0,1])
        p[x%z].append(x)
    
for i in range(z):
    for j in range(len(m[i])):
        q += m[i][j][0]*m[i][j][1]
print(q)
### BUGGY CODE ###

N,K = map(int,input().split())
ans = [0 for i in range(N+1)]
food = {}
food1 = []
for i in range(1,N+1):
    food[i] = 0
for i in range(N):
    t,d = map(int,input().split())
    food1.append((d,t))
food1.sort()
syurui = 0
sum = 0
x = []
for i in range(1,N+1):
    d,t = food1[-i]
    if food[t] == 0:
        if i > K:
            if len(x) == 0:
                break
        sum += d
        food[t] = 1
        syurui += 1
        if i > K:
            y = x.pop(0)
            sum -= y
    else:
        if i <= K:
            sum += d
            x.append(d)
            x.sort()
    if syurui == K:
        ans[K] = max(sum + K**2,ans[K])
        break
    else:
        ans[syurui] = max(sum + syurui**2,ans[syurui])
print(max(ans))

### FIXED CODE ###

N,K = map(int,input().split())
ans = [0 for i in range(N+1)]
food = {}
food1 = []
for i in range(1,N+1):
    food[i] = 0
for i in range(N):
    t,d = map(int,input().split())
    food1.append((d,t))
food1.sort()
syurui = 0
sum = 0
import heapq
x = []
heapq.heapify(x)
for i in range(1,N+1):
    d,t = food1[-i]
    if food[t] == 0:
        if i > K:
            if len(x) == 0:
                break
        sum += d
        food[t] = 1
        syurui += 1
        if i > K:
            y = heapq.heappop(x)
            sum -= y
    else:
        if i <= K:
            sum += d
            heapq.heappush(x,d)
    if syurui == K:
        ans[K] = max(sum + K**2,ans[K])
        break
    else:
        ans[syurui] = max(sum + syurui**2,ans[syurui])
print(max(ans))
### BUGGY CODE ###

m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=list(range(0,n1+1))
    ar=list(range(0,n2+1))
    for i in range(n1):
        el[i]=a[left+i]
    for i in range(n2):
        ar[i]=a[mid+i]
    el[n1]=float("inf")
    ar[n2]=float("inf")
    i=0
    j=0
    for k in range(left,right):
        global m
        m+=1
        if(el[i] <= ar[j]):
            a[k] = el[i]
            i=i+1
        else:
            a[k]=ar[j]
            j=j+1

def merge_sort(a,left,right):
    if(left+1<right):
        mid=(left+right)//2
        merge_sort(a,left,mid)
        merge_sort(a,mid,right)
        merge(a,left,mid,right)
    else:
        if(a[left]>a[right-1]):
            a[left],a[right-1]=a[right],a[left]



n=int(input())
s=input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)
    

### FIXED CODE ###

m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=a[left:mid]
    ar=a[mid:right]
    el.append(float("inf"))
    ar.append(float("inf"))
    i=0
    j=0
    for k in range(left,right):
        global m
        m+=1
        if(el[i] <= ar[j]):
            a[k] = el[i]
            i=i+1
        else:
            a[k]=ar[j]
            j=j+1

def merge_sort(a,left,right):
    if(left+1<right):
        mid=(left+right)//2
        merge_sort(a,left,mid)
        merge_sort(a,mid,right)
        merge(a,left,mid,right)
    else:
        if(a[left]>a[right-1]):
            a[left],a[right-1]=a[right],a[left]



n=int(input())
s=input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)
### BUGGY CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(N):
    lcm = lcm * a[i] // gcd(lcm, a[i])
ans = 0
for i in range(N):
    ans += (lcm//a[i])%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ans = 0
for i in a:
    ans += (lcm//i)#%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###


N,W = map(int,input().split())
wv = []
for i in range(N):
    a = list(map(int,input().split()))
    wv.append(a)
sumv = sum([i[1] for i in wv])

dp = [[float('inf') for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
maxb = []
for j in range(N+1):
    for i in range(sumv,-1,-1):
        if dp[j][i] <= W:
            maxb.append(i)
            break
print(maxb[-1])



### FIXED CODE ###

N,W = map(int,input().split())
wv = []
for i in range(N):
    a = list(map(int,input().split()))
    wv.append(a)
sumv = sum([i[1] for i in wv])
dp = [[10**10 for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]

for i in range(sumv,-1,-1):
    if dp[-1][i] <= W:
        print(i)
        break