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


def bisect(a,B,lo,hi):
    if hi-lo<=1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

A = [int(input()) for i in range(N)]

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B)-1)]=A[i]
print(len(B))

### FIXED CODE ###


def bisect(a,B,lo,hi):
    if hi-lo<=1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

A = [int(input()) for i in range(N)]

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B)-1)]=A[i]
print(len(B))
### BUGGY CODE ###

a,b,c=map(int,input().split())
ans=0
poison=False
while(True):
    if(poison):
        if(b>0):
            b-=1
            ans+=1
        elif(a>0):
            a-=1
        else:
            break
        poison=False
    else:
        if(c>0):
            c-=1
            ans+=1
            poison=True
        elif(b>0):
            b-=1
            ans+=1
        elif(a>0):
            a-=1
        else:
            break
print(ans)

### FIXED CODE ###

a,b,c=map(int,input().split())
if(c<=a+b):
	print(c+b)
else:
	print((a+b)+b+1)
### BUGGY CODE ###

from copy import copy


def main():
    N = int(input())
    A_lsit = [int(input()) for _ in range(N)]
    for i in range(N):
        tmp_list = copy(A_lsit)
        tmp_list.pop(i)
        print(max(tmp_list))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from copy import copy


def main():
    N = int(input())
    A_list = [int(input()) for _ in range(N)]
    tmp_list = copy(A_list)
    tmp_list.sort()
    max_num = tmp_list[-1]
    second_max_num = tmp_list[-2]
    max_index = A_list.index(max_num)
    for i in range(N):
        if i is max_index:
            print(second_max_num)
            continue
        print(max_num)


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

def get_sum(n, index, s, slist):
    if index == n:
        if s % 10 == 0:
            s = 0
        return s
    left = get_sum(n, index + 1, s + slist[index], slist)
    right = get_sum(n, index + 1, s, slist)
    return max(left, right)


N = int(input())
sl = []
for n in range(N):
    sl.append(int(input()))

sum = 0
index = 0
for s in sorted(sl)[::-1]:
    if (sum + s) % 10 == 0:
        break
    sum += s
    index += 1

print(get_sum(N, index, sum, sl))

### FIXED CODE ###

N = int(input())
sl = []
for n in range(N):
    sl.append(int(input()))

sum = sum(sl)
sorted_sl = sorted(filter(lambda s: s % 10 != 0,sl))
if len(sorted_sl) == 0:
    print(0)
    exit()
count = 0
while sum % 10 == 0 and count < len(sorted_sl):
    sum -= sorted_sl[count]
    count += 1

print(sum)
### BUGGY CODE ###

#300
N = int(input())
S = [input() for _ in range(N)]
L = [0 for _ in range(N)]
L1 = ["" for _ in range(N)]
S.sort()
k = 0


for i in range(N):
    if i == 0:
        L[k] = 1 
        L1[k] = S[i]
    else:
        if S[i-1] == S[i]:
            L[k] = L[k] + 1
        else:
            L[k+1] = 1
            L1[k+1] = S[i]
            k += 1

for i in range(N):
    if L[i] == max(L):
        print(L1[i])

### FIXED CODE ###

#300
N = int(input())
S = [input() for _ in range(N)]
L = [0 for _ in range(N)]
L1 = ["" for _ in range(N)]
S.sort()
k = 0


for i in range(N):
    if i == 0:
        L[k] = 1 
        L1[k] = S[i]
    else:
        if S[i-1] == S[i]:
            L[k] = L[k] + 1
        else:
            L[k+1] = 1
            L1[k+1] = S[i]
            k += 1

m = max(L)
for i in range(N):
    if L[i] == m:
        print(L1[i])
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, M, L = map(int, input().split())
dist = [[INF] * N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if c > L:
        continue
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c
Q = int(input())

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
fuel = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        fuel[i][j] = 1 if dist[i][j] <= L else INF
for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])
for i in range(Q):
    s,t = map(int, input().split())
    if fuel[s - 1][t - 1] != INF:
        print(fuel[s - 1][t - 1] - 1)
    else:
        print(-1)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, M, L = map(int, input().split())
dist = [[INF] * N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if c > L:
        continue
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c
Q = int(input())

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
fuel = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        fuel[i][j] = 1 if dist[i][j] <= L else INF
for k in range(N):
    for i in range(N):
        for j in range(N):
            if fuel[i][j] > fuel[i][k] + fuel[k][j]:
                fuel[i][j] = fuel[i][k] + fuel[k][j]
for i in range(Q):
    s,t = map(int, input().split())
    if fuel[s - 1][t - 1] != INF:
        print(fuel[s - 1][t - 1] - 1)
    else:
        print(-1)
### BUGGY CODE ###

import sys
from functools import lru_cache
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    dp = [[-1]*(N+1) for _ in range(N+1)]

    for i in range(N+1):
        dp[i][i] = 0

    for l in range(1,N+1):
        for i in range(N-l+1):
            j = i + l
            if (N-l)%2==0:
                dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])
            else:
                dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])

    print(dp[0][N])



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import lru_cache
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')

@lru_cache(maxsize=None)
def f(N, *A):
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][i] = 0
    for l in range(1, N + 1):
        for i in range(N - l + 1):
            j = i + l
            if (N - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
    print(dp[0][N])

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    f(N,*A)

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

import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=deque([0]*n)
l=deque()
l.append(0)
while l:
    x=l.pop()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)


### FIXED CODE ###

import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=deque([0]*n)
l=deque()
l.append(0)
while l:
    x=l.popleft()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += li[i]*li[j]
        ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0

for i in range(1, n):
    ans += li[0]*li[i]

check = ans
for i in range(1, n):
    if li[i-1] == 0:
        continue
    check -= li[i] * li[i-1]
    check //= li[i-1]
    check *= li[i]
    ans += check
    ans %= mod

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

s = input()
q = int(input())
for _ in range(q):
    com, *query = input().split()

    if com == "1":
        s = s[::-1]
    else:
        f, c = query
        if f == "1":
            s = c + s
        else:
            s = s + c

print(s)


### FIXED CODE ###

from collections import deque

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

inv = False
for _ in range(q):
    com, *query = input().split()
    if com == "1":
        if not inv:
            inv = True
        else:
            inv = False
    else:
        f, c = query
        if not inv:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)


s = "".join(s)
print(s if not inv else s[::-1])
### BUGGY CODE ###

import bisect


N = int(input())

lis = []

A1 = int(input())


lis.append(A1)


for i in range(N-1):

    A = int(input())

    flag = True
    ins = bisect.bisect_left(lis,A)

    if ins == 0:
        lis.insert(0,A)

    if lis[ins-1] < A:
        lis[ins-1] = A

"""
    for l in lis:

 

        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break

    if flag:
        lis.append(A)
"""

#print (lis)
print (len(lis))


### FIXED CODE ###

import bisect

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

A.reverse()

seq = [float("-inf")]

for i in A:

    ind = bisect.bisect_right(seq,i)

    if ind == len(seq):
        seq.append(i)
    else:
        seq[ind] = i

print (len(seq)-1)
### BUGGY CODE ###

import numpy as np
from numba import njit

N = int(input())
slimes = list(map(int, input().split()))
csum_slimes = [0]
for i in range(N):
    csum_slimes.append(csum_slimes[-1]+slimes[i])

dpt = np.full((N, N), -1, dtype='int64')

def get_min_cost(l, r):
    if dpt[l][r] != -1:
        return dpt[l][r]
    if l == r:
        return 0
    min_cost = 10**18
    for m in range(l, r):
        min_cost = min(min_cost, get_min_cost(l,m)+get_min_cost(m+1,r)+csum_slimes[r+1]-csum_slimes[l])
    dpt[l][r] = min_cost
    return min_cost
    

print(get_min_cost(0, N-1))

### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
slimes = np.array(list(map(int, input().split())), dtype='int64')
csum_slimes = [0]
for i in range(N):
    csum_slimes.append(csum_slimes[-1]+slimes[i])
csum_slimes = np.array(csum_slimes, dtype='int64')

dpt = np.full((N, N), -1, dtype='int64')

@njit(cache=True)
def get_min_cost(l, r, slimes, dpt, csum_slimes):
    if dpt[l][r] != -1:
        return dpt[l][r]
    if l == r:
        return 0
    min_cost = 10**18
    for m in range(l, r):
        min_cost = min(min_cost, get_min_cost(l,m,slimes,dpt,csum_slimes)+get_min_cost(m+1,r,slimes,dpt,csum_slimes)+csum_slimes[r+1]-csum_slimes[l])
    dpt[l][r] = min_cost
    return min_cost
    

print(get_min_cost(0, N-1, slimes, dpt, csum_slimes))
### BUGGY CODE ###

import sys

H, W, M = map(int,input().split())
R = [0] * H
C = [0] * W
S = set()
for _ in range(M):
    h, w = map(int,input().split())
    S.add((h-1, w-1))
    R[h-1] += 1
    C[w-1] += 1

r = max(R)
c = max(C)

for h in [i for i in range(H) if R[i] == r]:
    for w in [i for i in range(W) if C[i] == c]:
        if not (h, w) in S:
            print(r + c)
            sys.exit()

print(r + c - 1)

### FIXED CODE ###

import sys

H, W, M = map(int,input().split())
R = [0] * H
C = [0] * W
S = set()
for _ in range(M):
    h, w = map(int,input().split())
    S.add((h-1, w-1))
    R[h-1] += 1
    C[w-1] += 1

r = max(R)
c = max(C)

HL = [i for i in range(H) if R[i] == r]
WL = [i for i in range(W) if C[i] == c]

for h in HL:
    for w in WL:
        if not (h, w) in S:
            print(r + c)
            sys.exit()

print(r + c - 1)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp[i+1][j|c] = min(dp[i][j|c], dp[i][j] + a, dp[i+1][j|c])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

print([dp[-1][-1], -1][dp[-1][-1] == float("inf")])

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp[i+1][j|c] = min(dp[i][j|c], dp[i][j] + a, dp[i+1][j|c])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

print([dp[-1][-1], -1][dp[-1][-1] == float("inf")])
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
def m(n):
    return min(P[:n+1])
A=[]
for i in range(N):
    A.append(m(i))
print(len(set(A)))

### FIXED CODE ###

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

ans = 0
n_min = 0
for i in range(0,n):
    if i == 0:
        ans += 1
        n_min = p[i]
        continue
    if p[i] <= n_min:
        ans += 1
        n_min = p[i]
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

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

ans_x, ans_y, ans_z = -1, -1, -1

n_list = np.append([0], range(N+1))
n_list = np.append(n_list, [N])

#print(n_list)
#print(len(n_list))
#print(range(len(n_list)))
#print(range(10 ,len(n_list)))

for i in range(len(n_list)) :
  x = n_list[i]
  for j in range(i+1 ,len(n_list)) :
    y = n_list[j] - x
    z = N - x - y
    sum = 10000*x + 5000*y + 1000*z
    #print("tameshi : " + str(x) + " " + str(y) + " " + str(z))
    if sum == Y and x>=0 and y>=0 and z>=0 :
      print(str(x) + " " + str(y) + " " + str(z))
      sys.exit(0)

print(str(ans_x) + " " + str(ans_y) + " " + str(ans_z))

### FIXED CODE ###

import sys
#import numpy as np

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

ans_x, ans_y, ans_z = -1, -1, -1

#n_list = np.append([0], range(N+1))
#n_list = np.append(n_list, [N])

#print(n_list)
#print(len(n_list))
#print(range(len(n_list)))
#print(range(10 ,len(n_list)))

for i in range(N+1) :
  x = i
  #sum = 10000*x
  #if sum > Y :
  #  continue

  for j in range(N+1-x) :
    y = j
    z = N - x - y
    sum = 10000*x + 5000*y + 1000*z
    #print("tameshi : " + str(x) + " " + str(y) + " " + str(z))
    if sum == Y :
      ans_x=x
      ans_y=y
      ans_z=z

print(str(ans_x) + " " + str(ans_y) + " " + str(ans_z))
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(1,N+1):
    p *= i
print(p%1000000007)

### FIXED CODE ###

N = int(input())
p = 1
for i in range(1,N+1):
    p *= i
    p %= 1000000007
print(p)
### BUGGY CODE ###

import fractions
from functools import reduce


def gcd(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
*A, = map(int, input().split())
ans = 0
for i in range(N):
    b = A[:i]+A[i+1:]
    g = gcd(b)
    if g > ans:
        ans = g
print(ans)


### FIXED CODE ###

import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


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

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)
### BUGGY CODE ###

def kaijo(a):
    if a == 0:
        return 1
    return a*kaijo(a-1)

def sosu_num(a):
    count = 0
    for i in range(1, a+1):
        if a % i == 0:
            count += 1
    return count % (10**9 + 7)

N = int(input())
print(sosu_num(kaijo(N)))

### FIXED CODE ###

import math
 
N = int(input())
mod = 10**9+7
 
def get_primes(n):
    ps = [0, 0] + [i for i in range(2, n+1)]
    for i in range(2, n+1):
        if ps[i] == 0:
            continue
        for j in range(i * i, n+1, i):
            ps[j] = 0
    return [p for p in ps if p]
 
 
prime = get_primes(N)
 
ans = 1
for p in prime:
    tmp = 0
    for i in range(1, int(math.log(N, p))+1):
        tmp += N // (p**i)
 
    ans = (ans * (tmp + 1)) % mod
 
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = str(input())
MOD = 1000000007

dp = [0 for i in range(13)]
dp[0] = 1
for i in range(0, len(S)):
    next_dp = [0 for i in range(13)]
    if S[len(S) - i - 1] == '?':
        for k in range(10):
            for j in range(13):
                add = k * pow(10,i) % 13
                next_dp[(j + add) % 13] += dp[j]
    else:
        for j in range(13):
            add = int(S[len(S) - i - 1]) * pow(10,i) % 13
            next_dp[(j + add) % 13] = dp[j]
    dp = next_dp

print(dp[5] % MOD)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
dp[0] = 1
mul = 1
for i in range(0, N):
    next_dp = [0] * 13
    if S[N - i - 1] == '?':
        next_dp = [sum(dp[(j - k * mul) % 13] for k in range(10)) for j in range(13)]
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
    dp = [d % MOD for d in next_dp]
    mul *= 10
    mul %= 13

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

from bisect import bisect_left
N, M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
for i in range(M):
  tmp=A[-1]//2
  A.pop(N-1)
  A.insert(bisect_left(A, tmp), tmp)
  if A[-1]==0:
    break
print(sum(A))

### FIXED CODE ###

import heapq
N, M=map(int, input().split())
A=list(map(int, input().split()))
A=list(map(lambda x: -x, A))
heapq.heapify(A)
for i in range(M):
  heapq.heappush(A, (heapq.heappop(A)+1)//2)
print(-sum(A))
### BUGGY CODE ###

x,y = map(int,input().split())
li = list(map(int,input().split()))
from collections import deque
l = []
for i in range(len(li)):
    l.append((1+ li[i])/2)
M = 0

for i in range(len(l)-y+1):
    ll = l[i:i+y]
    m=0
    for k in range(y):
        m += ll[k]
    if m > M:
            M = m
print(M)

### FIXED CODE ###

x,y = map(int,input().split())
li = list(map(int,input().split()))
from collections import deque
l = []
for i in range(len(li)):
    l.append((1+ li[i])/2)
from itertools import accumulate
a = list(accumulate(l))
M = a[y-1]
for i in range(len(a)-y):
    m = a[i+y] - a[i]
    if m > M:
        M = m
print(M)
### BUGGY CODE ###

# tenka1-2017-beginnerC - 4/N
# exhaustive search
def main():
    N = int(input())
    for h in range(1, 3501):
        for n in range(1, 3501):
            numerator = N * h * n
            denominator = 4 * h * n - N * n - N * h
            if denominator > 0 and numerator % denominator == 0:
                w = numerator // denominator
                print(h, n, w)
                return


if __name__ == "__main__":
    main()

### FIXED CODE ###

# tenka1-2017-beginnerC - 4/N
# exhaustive search
def main():
    N = int(input())
    for h in range(1, 3501):
        for n in range(1, 3501):
            numerator = N * h * n
            denominator = 4 * h * n - N * n - N * h
            if denominator > 0 and numerator % denominator == 0:
                w = numerator // denominator
                print(h, n, w)
                return


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

#45 C - Scc Puzzle
N,M = map(int,input().split())
if M//N < 2:
    print(M//2)
else:
    for i in range(M//2+1):
        if M//N < 2:
            break   
        M -= 2
        N += 1
    print(N-1)

### FIXED CODE ###

N,M = map(int,input().split())
if M//N < 2:
    print(M//2)
else:
    # 交換できる回数の最大値は M - 2x = 2*(N + x) より求めた
    x = (M-2*N)//4
    print(N+x)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cnt = d = 0 
z = []
while True:
  cnt += 1
  if a[d] == 2:
    print(cnt)
    break
  elif a[d] in z:
    print(-1)
    break
  else:
    z.append(a[d])
    d = a[d] - 1


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cnt = d = 0 
while True:
  cnt += 1
  if a[d] == 2:
    print(cnt)
    break
  elif cnt >= 10**5:
    print(-1)
    break
  else:
    d = a[d] - 1
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
ans = 0
sushi = defaultdict(list)

for _ in range(n):
    t, d = map(int, input().split())
    sushi[t].append(d)

most_tasty = []
other_sushi = []

for key, value in sushi.items():
    value.sort(reverse=True)
    most_tasty.append(value[0])
    value.pop(0)
    for v in value:
        other_sushi.append(v)

most_tasty.sort(reverse=True)
other_sushi.sort(reverse=True)
for i in range(1, k + 1):
    num = min(i, len(most_tasty))
    point = sum(most_tasty[:num])
    point += sum(other_sushi[:(k - num)])
    point += num ** 2
    ans = max(ans, point)

print(ans)


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
top = [0] * n
sub = []

for i in range(n):
    t, d = map(int, input().split())
    t -= 1
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)

print(ans)