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

import bisect
from collections import deque
import copy

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

node_dic = {}
for _ in range(N - 1):
    u, v = map(int, input().split())
    if u in node_dic:
        node_dic[u].append(v)
    else:
        node_dic[u] = [v]

    if v in node_dic:
        node_dic[v].append(u)
    else:
        node_dic[v] = [u]

# print(node_dic)

use_array = [-1] * N
ans_array = [0] * N

edge_array = deque([(1, [0])])
use_array[0] = 1

while(len(edge_array)):
    edge, arr = edge_array.popleft()
    # print(edge, arr, ans_array)

    insert = bisect.bisect_left(arr, a_array[edge - 1])
    if insert == len(arr):
        arr.append(a_array[edge - 1])
    else:
        arr[insert] = a_array[edge - 1]
    ans_array[edge - 1] = len(arr) - 1
    for next_edge in node_dic[edge]:
        if use_array[next_edge - 1] == -1:
            use_array[next_edge - 1] = 1
            arr_next = copy.deepcopy(arr)
            edge_array.append((next_edge, arr_next))

print("\n".join(map(str, ans_array)))


### FIXED CODE ###

import sys
import bisect


def dfs(edge):
    insert = bisect.bisect_left(lis_array, a_array[edge - 1])
    old = lis_array[insert]
    lis_array[insert] = a_array[edge - 1]
    ans = bisect.bisect_left(lis_array, INF)
    ans_array[edge - 1] = ans
    for next_edge in node_dic[edge]:
        if use_array[next_edge - 1] == -1:
            use_array[next_edge - 1] = 1
            dfs(next_edge)
    lis_array[insert] = old


sys.setrecursionlimit(10 ** 9)
N = int(input())
a_array = list(map(int, input().split()))

node_dic = {}
for _ in range(N - 1):
    u, v = map(int, input().split())
    if u in node_dic:
        node_dic[u].append(v)
    else:
        node_dic[u] = [v]

    if v in node_dic:
        node_dic[v].append(u)
    else:
        node_dic[v] = [u]

# print(node_dic)

use_array = [-1] * N
ans_array = [0] * N

INF = 2 * 10 ** 9
lis_array = [INF] * N

use_array[0] = 1
dfs(1)
print("\n".join(map(str, ans_array)))
### BUGGY CODE ###

import sys
import queue
bbn=1000000007
	
#+++++
		
def main():
	n, k = map(int, input().split())
	al=list(map(int, input().split()))
	fl=list(map(int, input().split()))
	
	qq=queue.PriorityQueue()
	
	al.sort(reverse=True)
	fl.sort()
	for a,f in zip(al,fl):
		qq.put((-a*f, a, f))
	
	#while not qq.empty():
	#	a=qq.get()
	#	pa(a)
	
	for i in range(k):
		c,a,f=qq.get()
		if a == 0:
			return 0
		an=a-1
		qq.put((-an*f, an, f))		
		
	c,a,f = qq.get()
	print(-c)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import queue
bbn=1000000007
	
#+++++

def can_finish(time, a_c_qq, a_k):
	kc=a_k
	
	#if time==12:
	#	print(*a_c_qq)
		
	for (st,a,f) in (a_c_qq):
		if st <= time:
			return True
		
		#time => f*a' を目指す。
		#a' <= time / f が必要。
		#コストは a - (time // f)
		kc -= a - (time//f)
		#if time==12:
		#	pa((st,a,f, time,(time//f),a- (time//f),kc))
		
		if kc < 0:
			return False
		
	return True
	
		
def main():
	n, k = map(int, input().split())
	al=list(map(int, input().split()))
	fl=list(map(int, input().split()))
	
	qq=queue.PriorityQueue()
	
	al.sort(reverse=True)
	fl.sort()
	qq=[(a*f,a,f) for a,f in zip(al,fl)]
	qq.sort(reverse=True)

	#while not qq.empty():
	#	a=qq.get()
	#	pa(a)
	
	ok_max,_,_=qq[0]
	if sum(al) <= k:
		return 0
	ng_min=0
	
	while ok_max - ng_min > 1:
		mid = (ok_max + ng_min)// 2
		can_do = can_finish(mid, qq, k)
		#pa((ok_max,ng_min,mid,can_do))
		if can_do:
			ok_max = mid
		else:
			ng_min = mid

	print(ok_max)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

a = int(input())
ar = list(input())
br = []
for i in range(a):
    count = 0
    wr = ar[0:i]
    er = ar[i:a]
    count += wr.count("W")
    count += er.count("E")
    br.append(count)
print(min(br))

### FIXED CODE ###

a = int(input())
ar = list(input())
wc = 0
ec = ar.count("E")
br = []
for i in range(a):
    if ar[i] == "E":
        ec -= 1
    br.append(ec + wc)
    if ar[i] == "W":
        wc += 1
print(min(br))
### BUGGY CODE ###

n=int(input())
a=[int(i)for i in input().split()]
res=0
for i in range(n-1):
    for j in range(i+1,n):
        res+=(a[i]*a[j])%(1000000000+7)
print(res%(1000000000+7))

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
mod=10**9+7
res=0
for i in a:
    s-=i
    res+=i*s%mod
print(res%mod)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

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

for j in range(N):
    if K-Q+A.count(j)>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

n = int(input())
s = str(input())

r = [i for i in range(n) if s[i] == 'R']
g = [i for i in range(n) if s[i] == 'G']
b = [i for i in range(n) if s[i] == 'B']
cnt = 0

for i in r:
    for j in g:
        for k in b:
            num = [i, j, k]
            num.sort()
            if num[1]-num[0]==num[2]-num[1]:
                continue
            cnt += 1

print(cnt)


### FIXED CODE ###

from itertools import product as pro

n = int(input())
s = str(input())

r = [i for i in range(n) if s[i] == 'R']
g = [i for i in range(n) if s[i] == 'G']
b = [i for i in range(n) if s[i] == 'B']
cnt = len(r)*len(g)*len(b)

length = max(len(r), len(g), len(b))
if length == len(r):
    max1 = set(r)
    min1 = g
    min2 = b

if length == len(g):
    max1 = set(g)
    min1 = r
    min2 = b

if length == len(b):
    max1 = set(b)
    min1 = g
    min2 = r

for i, j in pro(min1, min2):
    if 2*j-i in max1:
        cnt -= 1
    if 2*i-j in max1:
        cnt -= 1
    if (i+j)/2 in max1:
        cnt -= 1

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

n = input()

n = int(n)
s = [0]*n
sm = []

for i in range(0,n):
  s[i] = input()

for i in range(0,n):
  c = 1
  sm.insert(0,s[i])
  if(sm.count(s[i]) > 1):
    del sm[0]

print(len(sm))

### FIXED CODE ###

n = int(input())
s = [0]*n

for i in range(n):
  s[i] = input()
ans = 0
s.sort()
for i in range(n-1):
  if s[i] != s[i+1]:
    ans += 1
    
print(ans+1)
### BUGGY CODE ###

import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
N = int(input())
a = readints()
ans = [0]*(N+1)
for i in range(len(a)):
    for j in range(1, N+1):
        if a[i] == j:
            ans[j] += 1
for i in range(len(ans)-1):
    print(ans[i+1])


### FIXED CODE ###

import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
N = int(input())
a = readints()
ans = [0]*(N+1)
for i in range(len(a)):
    ans[(a[i])] += 1
for i in range(len(ans)-1):
    print(ans[i+1])
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
res = 0
for c in range(1,k+1):
    for b in range(1,k+1):
        for a in range(1,k+1):
            res += gcd(a,b,c)
print(res)

### FIXED CODE ###

import math
from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

k = int(input())
res = 0
for c in range(1,k+1):
    for b in range(1,k+1):
        gcd_cd = math.gcd(c,b)
        for a in range(1,k+1):
            # res += gcd(a,b,c)
            gcd_abc = math.gcd(a,gcd_cd)
            res += gcd_abc
print(res)
### BUGGY CODE ###

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

N = int(input())
for i in range(1, N+1):
    if i < 6:
        print(0)
        continue
    cnt = 0
    for x in range(1, 20):
        for y in range(1, 20):
             D = (((x+y)**2 - 4*(x**2+y**2+x*y-i)) ** (1/2))
             if ((x+y)**2 - 4*(x**2+y**2+x*y-i)) > 0 :
                 Z = (-(x+y) + D) / 2
                 if is_integer(Z) and Z>0:
                     cnt += 1
    print(cnt)

### FIXED CODE ###

N = int(input())
lis = [0]*N
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x -1
            if ans >= N:
                pass
            else:
                lis[ans] += 1
for i in range(N):
    print(lis[i])
### BUGGY CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(300000)

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

for j in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

visited = [False] * N


def dfs(parent):
    visited[parent] = True
    for child in tree[parent]:
        if not visited[child]:
            counter[child] += counter[parent]
            dfs(child)


dfs(0)
print(' '.join(map(str, counter)))


### FIXED CODE ###

from collections import defaultdict, deque

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

for j in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

visited = [False] * N

queue = deque()
queue.append(0)
while queue:
    parent = queue.popleft()
    visited[parent] = True
    for child in tree[parent]:
        if not visited[child]:
            counter[child] += counter[parent]
            queue.append(child)

print(' '.join(map(str, counter)))
### BUGGY CODE ###

while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[y][x] == "."):
            for h in xrange(y+1,H+1):
                ans = max(ans, min(s[x] for s in space[y:h])*(h-y))
    print ans

### FIXED CODE ###

def re_push(stack,num):#re_push and return max
    count = 0
    pre = num
    ma = 0
    while True:
        count += 1
        cur = stack.pop()
        if cur <= num:
            ma = max(ma,(count-1) * pre)
            stack += [cur]
            stack += [num]*(count-1)
            break
        if cur < pre:
            ma = max(ma,(count-1) * pre)
            stack += [cur]*count
            count = 0
        pre = cur
    return ma
            
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    table = [[0]*(W+1) for _ in xrange(H)]
    for y in xrange(H-1,-1,-1):
        for x in (x for x in xrange(W-1,-1,-1) if field[y][x] != "*"):
            table[y][x] = table[y][x+1] + 1
    ma = 0
    for x in xrange(W):
        stack = [0,table[0][x]]
        for y in xrange(1,H):
            if table[y-1][x] > table[y][x]:
                ma = max(ma, re_push(stack,table[y][x]))
            stack.append(table[y][x])
        ma = max(ma, re_push(stack,0))
    print ma
### BUGGY CODE ###

import math

k = int(input())
total = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            total += math.gcd( math.gcd(i,j), m)
print(total)


### FIXED CODE ###

import math
k = int(input())
total = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ab = math.gcd(a,b)
            total += math.gcd(ab, c)
print(total)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        l[i] = A
        ans[v] = l.index(inf)
        visited[v] = True

for i in range(1,N+1):
    print(ans[i])







### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

import sys
dp = { 0:0, 1:1, 2:1 }
N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num):
    if num in dp:
        return dp[num]
    
    b = bin(num)
    popcount = b.count('1')
    
    if num % popcount == 0:
        dp[num] = 1
    else:
        dp[num] = 1 + f(num % popcount)

    return dp[num]

nX = int(X, 2)
for i in range(0, N):
    if X[i] == '0':
        print(f(nX + 2**(N-i-1)))
    else:
        print(f(nX - 2**(N-i-1)))

### FIXED CODE ###

import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

#nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())

x = 0
now = 0
result = 0
for i in range(n+1):
    x = i
    if x >b:
        continue
    now = (((a * x)//b)) - (a * (x//b))
    #now = math.ceil(((a * x)/b)) - (a * math.ceil(x/b))
    #print("now=",now,"x=",x)
    #print(result,now)
    result = max(result,now)

print(result)
    



### FIXED CODE ###


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

x = min(b-1,n)

print((((a * x)//b)) )
### BUGGY CODE ###

n=int(input())
b = ''
for i in range(n):
    b += (input() + ' ')
a = list(b.split())
a_count = [a.count(i) for i in a]
print('\n'.join(sorted(set([a[i] for i in range(len(a_count)) if a_count[i] == max(a_count)]))))


### FIXED CODE ###

d=dict()
for i in range(int(input())):
    s=input()
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
max_v = max(d.values())
print(*sorted([kv[0] for kv in d.items() if kv[1] == max_v]))
### BUGGY CODE ###

a, b, x = map(int, input().split())

ans = 0

for i in range(0, b//x+1):
    xi = x * i
    if xi >= a and xi <= b:
        # print(xi)
        ans += 1
    if xi > b:
        break

print(ans)


### FIXED CODE ###

a, b, x = map(int, input().split())

# ans = 0
bx = b//x + 1
ax = (a-1)//x + 1
ans = bx - ax
print(ans)
### BUGGY CODE ###

N = int(input())
lists = []
result = 0
for i in range(N):
    lists.append(input())

sortedlist = []
for i in range(0, N):
    sortedlist.append(sorted(lists[i]))

sortedlist.sort()
for i in range(0, N):
    for j in range(i + 1, N):
        if sortedlist[i] == sortedlist[j]:
            result += 1
        else:
            break

print(result)


### FIXED CODE ###

import math

N = int(input())
lists = []
result = 0
tempres = 0
for i in range(N):
    lists.append(input())

sortedlist = []
for i in range(0, N):
    sortedlist.append(sorted(lists[i]))

sortedlist.sort()
for i in range(0, N):
    if tempres != 0:
        tempres -= 1
        result += tempres
        continue

    for j in range(i + 1, N):
        if sortedlist[i] == sortedlist[j]:
            tempres += 1
        else:
            break
    result += tempres

print(result)
### BUGGY CODE ###

n = int(input())
nn = (n + 1) / 2
s = [0]*n
print(0)
s[0] = input()
if s[0] == "Vacant":
    exit()
print(n-1)
s[n-1] = input()
if s[n-1] == "Vacant":
    exit()
ll = 0
hh = nn-1
while hh - ll > 1:
    l = ll*2
    h = hh*2
    ii = (ll + hh) / 2
    i = ii*2
    print(i)
    s[i] = input()
    if s[i] == "Vacant":
        exit()
    elif s[i] != s[l]:
        ll = ii
    else:
        hh = ii
print(ll+hh)

### FIXED CODE ###

n = int(input())
nn = (n + 1) // 2
s = [0]*n
print(0)
s[0] = input()
if s[0] == "Vacant":
    exit()
print(n-1)
s[n-1] = input()
if s[n-1] == "Vacant":
    exit()
ll = 0
hh = nn-1
while hh - ll > 1:
    l = ll*2
    h = hh*2
    ii = (ll + hh) // 2
    i = ii*2
    print(i)
    s[i] = input()
    if s[i] == "Vacant":
        exit()
    elif s[i] != s[l]:
        hh = ii
    else:
        ll = ii
print(ll+hh)
### BUGGY CODE ###

sn, tn, *s = map(int, open(0).read().split())
sy_oi = [[s[i * 2], s[i * 2 + 1]] for i in range(sn)]
sy_oi.sort(key=lambda x: -x[1])
cho = sy_oi[tn - 1::-1]
zan = sy_oi[tn:]
zn = sn - tn
# チョイスした種類の辞書
sydic = {}
for x in cho:
    if x[0] in sydic:
        sydic[x[0]] += 1
    else:
        sydic[x[0]] = 1
ot = sum([x[1] for x in cho])  # おいしさポイント
mt = len(sydic)  # まんぞくポイント
ans = ot + mt ** 2
zi = 0
cnt = 0
while 1:
    # チョイスから削除できるものを探す
    for i in range(tn - cnt):
        if sydic[cho[i][0]] > 1:
            sydic[cho[i][0]] -= 1
            ot -= cho[i][1]
            del cho[i]
            break
    else:
        break
    # 残から加えるものを探す
    for i in range(zi, zn):
        if zan[i][0] not in sydic:
            sydic[zan[i][0]] = 1
            ot += zan[i][1]
            mt += 1
            zi = i
            break
    else:
        break
    # 得点計算して更新
    ans = max(ans, ot + mt ** 2)
    cnt += 1
print(ans)


### FIXED CODE ###

sn, tn, *s = map(int, open(0).read().split())
sy_oi = [[s[i * 2], s[i * 2 + 1]] for i in range(sn)]
sy_oi.sort(key=lambda x: -x[1])
cho = sy_oi[tn - 1::-1]
zan = sy_oi[tn:]
zn = sn - tn
# チョイスした種類の辞書
sydic = {}
for x in cho:
    if x[0] in sydic:
        sydic[x[0]] += 1
    else:
        sydic[x[0]] = 1
ot = sum([x[1] for x in cho])  # おいしさポイント
mt = len(sydic)  # まんぞくポイント
ans = ot + mt ** 2
ci = 0
zi = 0
while 1:
    # チョイスから削除できるものを探す
    for i in range(ci, tn):
        if sydic[cho[i][0]] > 1:
            sydic[cho[i][0]] -= 1
            ot -= cho[i][1]
            ci = i + 1
            break
    else:
        break
    # 残から加えるものを探す
    for i in range(zi, zn):
        if zan[i][0] not in sydic:
            sydic[zan[i][0]] = 1
            ot += zan[i][1]
            mt += 1
            zi = i + 1
            break
    else:
        break
    # 得点計算して更新
    ans = max(ans, ot + mt ** 2)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
for i in range(N):
  for j in range(i+1,N):
    ans+=(A[i]^A[j])
print(ans%(10**9+7))

### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
l=len(format(A.max(),'b'))
MOD=10**9+7

tei=1
ans=0
for i in range(l):
  B=(A >> i) & 1
  one=np.count_nonzero(B)
  zero=N-one
  ans+=tei*one*zero
  tei*=2
print(ans%MOD)
### BUGGY CODE ###

i = list(map(int, input().split()))
A = i[0]
B = i[1]
N = i[2]
a = -10 ** 20
for x in range(1, N+1):
  s = A * x // B
  t = A * (x // B)
  if s - t > a:
    a = s - t
print(a)    


### FIXED CODE ###

i = list(map(int, input().split()))
A = i[0]
B = i[1]
N = i[2]
if N < B-1:
    print(A * N // B)
else:
    print(A * (B-1) // B)