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

def main():
    X, K, D = map(int, input().split())

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 4
    else :
        limit = 5
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif X == 0 :
        if limit == 4 :
            print('0')
        else :
            print(abs(D))
    else :
        syo = X // D
        #print(syo)
        if syo > 1 :
            val[0] = X - (syo-2) * D
            #print(val[0])
            K = K -(syo-2)
            if K % 2 == 0:
                limit = 0
            else:
                limit = 1
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            #print(val[i+1])
            if (abs(val[i+1]) == abs(val[i-1])) and i > limit :
                #print("a")
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                #print("b")
                print(abs(val[i]))
                break


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, K, D = map(int, input().split())

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 4
    else :
        limit = 5
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif X == 0 :
        if limit == 4 :
            print('0')
        else :
            print(abs(D))
    else :
        syo = abs(X) // D
        #print(syo)
        if syo > 3 :
            if X > 0 :
                val[0] = X - (syo-2) * D
            else :
                val[0] = X + (syo - 2) * D
            #print(val[0])
            K = K -(syo-2)
            if K % 2 == 0:
                limit = 2
            else:
                limit = 3
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            #print(val[i+1])
            if (abs(val[i+1]) == abs(val[i-1])) and i > limit :
                #print("a")
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                #print("b")
                print(abs(val[i]))
                break


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

match = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = [int(_) for _ in input().split()]
dp = ['-1']*(n+10)
dp[0] = ''
for i in range(n+1):
    if dp[i]=='-1':
        continue
    else:
        for j in a:
            dp[i+match[j]]=str(max(int(dp[i+match[j]]),int(dp[i]+str(j))))
print(dp[n])

### FIXED CODE ###

match = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = [int(_) for _ in input().split()]
dp = [-1]*(n+10)
dp[0] = 0
for i in range(n+1):
    if dp[i]== -1:
        continue
    else:
        for j in a:
            dp[i+match[j]]= max(dp[i+match[j]],dp[i]*10+j)
print(dp[n])
### BUGGY CODE ###

def main():
    n = int(input())
    a_lst = list(map(int, input().split()))
    a_min = min(a_lst)
    a_max = max(a_lst)

    count_lst = []
    for num in range(a_min, a_max + 1):
        count = 0
        count += a_lst.count(num - 1)
        count += a_lst.count(num)
        count += a_lst.count(num + 1)
        count_lst.append(count)

    maximum = max(count_lst)
    print(maximum)


if __name__ == '__main__':
    main()

### FIXED CODE ###

n = int(input())
a_lst = list(map(int, input().split()))
for i in range(n):
    a_lst[i] += 1

max_a = max(a_lst)
count_lst = [0] * (max_a + 2)


for i in range(n):
    a = a_lst[i]
    index1 = a - 1
    index2 = a
    index3 = a + 1

    count_lst[index1] += 1
    count_lst[index2] += 1
    count_lst[index3] += 1

maximum = max(count_lst)
print(maximum)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
curmin = min(A)

for _ in range(M):
  b,c = map(int,input().split())
  if c <= curmin: continue

  cnt = 0
  while cnt < b and len(A)>0:
    a = heapq.heappop(A)
    if a >= c:
      heapq.heappush(A,a)
      break
    cnt += 1

  for _ in range(cnt):
    heapq.heappush(A,c)

  curmin = min(A[0], c)

print(sum(A))

### FIXED CODE ###

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

cards = []
for _ in range(M):
  b,c = map(int,input().split())
  cards.append([c,b])
cards.sort(key=lambda x: -x[0])

res = 0
idx = 0
left = cards[idx][1]
for i,a in enumerate(A):
  if a > cards[idx][0]:
    res += sum(A[i:])
    break
  else:
    res += cards[idx][0]

    left -= 1
    if left <= 0:
      idx += 1
      if idx >= M:
        if i+1 < N:
          res += sum(A[i+1:])
        break
      else:
        left = cards[idx][1]

print(res)
### BUGGY CODE ###

import itertools
while True:
    n,s=map(int,input().split())
    if n==0 and s==0:
        break
    num=[i for i in range(0,s+1)]
    print(num)
    ans=0
    comb=itertools.combinations(num,n)
    for c in comb:
        if sum(c) == s:
            ans +=1
    print(ans)


### FIXED CODE ###

def counter(rest, n, acc, to):
  if rest == 0:return acc == to
  if n == 10:return 0 
  return counter(rest - 1, n + 1, acc + n , to) + counter(rest, n + 1, acc, to)
 
while True:
  n, s = map(int, input().split())
  if not n:
    break
  print(counter(n, 0, 0, s))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b,ans = sorted(a),0
for i in range(n):
	if i%2!=b.index(a[i])%2: ans+=1
print(ans//2)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b,ans = [],0
for i,x in enumerate(a): b.append([x,i])
b.sort()
for i in range(n):
	if i%2!=b[i][1]%2: ans+=1
print(ans//2)
### BUGGY CODE ###

l, r = map(int, input().split())
ans = 2020
for i in range(l, r):
    for j in range(i+1, r+1):
        tmp = i * j % 2019
        ans = tmp if tmp < ans else ans
        if ans == 0:
            break

print(ans)


### FIXED CODE ###

l, r = map(int, input().split())
ans = 2020
if l <= (l // 2019 + 1) * 2019 <= r:
    ans = 0
else:
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            tmp = i * j % 2019
            ans = tmp if tmp < ans else ans
            if ans == 0:
                break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
L = [0 for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
s, t = map(int, input().split())
S = 3 * (s-1)
T = 3 * (t-1)

Frontier = [S]
Explored = []
while Frontier:
    v = Frontier.pop(0)
    l = L[v]
    Explored.append(v)
    next = G[v]
    if T in next:
        print((L[v] + 1) // 3)
        exit();
    for i in next:
        if i not in Explored:
            Frontier.append(i)
            L[i] = l + 1

print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
L = [-3 for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
s, t = map(int, input().split())
S = 3 * (s-1)
T = 3 * (t-1)

L[S] = 0
Frontier = [S]
while Frontier:
    v = Frontier.pop(0)
    for i in G[v]:
        if L[i] < 0:
            Frontier.append(i)
            L[i] = L[v] + 1

print(L[T]//3)
### BUGGY CODE ###

from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
B = [list(stdin.readline().rstrip()) for _ in range(H)]

q = queue.Queue()

for k in range(H):
    for l in range(W):
        if B[k][l] == '#':
            q.put((k, l, 0))

while not q.empty():
    h, w, t = q.get()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.put((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.put((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.put((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.put((h, w + 1, t + 1))
    if q.empty():
        print(t)


### FIXED CODE ###

from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
B = [list(stdin.readline().rstrip()) for _ in range(H)]

q = deque([])

for k in range(H):
    for l in range(W):
        if B[k][l] == '#':
            q.append((k, l, 0))

while len(q) > 0:
    h, w, t = q.popleft()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.append((h, w + 1, t + 1))
    if len(q) == 0:
        print(t)
### BUGGY CODE ###

n, k = map(int, input().split())
# n, k = map(int, "2 6".split())

while True:
    nc = n
    n = n - k
    if n <= 0:
        if abs(n) < nc:
            print(abs(n))
            break
        else:
            print(nc)
            break


### FIXED CODE ###

n, k = map(int, input().split())
# n, k = map(int, "2 6".split())
q = n // k #答え
mod = n % k #あまり

if q == 0:

    while True:
        nc = n
        n = n - k
        if n <= 0:
            if abs(n) < nc:
                print(abs(n))
                break
            else:
                print(nc)
                break
else:
    n1 = abs(n - (q * k))
    n2 = abs(n - ((q + 1) * k))
    if n1 < n2:
        print(n1)
    else:
        print(n2)
### BUGGY CODE ###

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

li = [input() for i in range(q)]

k= 0

for i in li:
    if i == "1":
        k += 1
    else:
        
        if (int(i[2])+k) % 2 == 0:
            s = s + i[4]
        else:
            s = i[4] + s

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

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

li = [input() for i in range(q)]
k = 0
ans = [s]
ans = deque(ans)

for i in li:
    if i == "1":
        k += 1
    else:
        if (int(i[2]) + k) % 2 == 0:
            ans.append(i[4])
        else:
            ans.appendleft(i[4])

ans = list(ans)
s = "".join(ans)
if k % 2 == 0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

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

l = len(set(a))
l2 = 0 if len([a.count(x) for x in set(a)]) % 2 else 1
print(l - l2)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

s = set(a)
l = len(s)
l2 = 0 if l % 2 else 1
print(l - l2)
### BUGGY CODE ###

N = int(input())
A = list(input().split())
ans = 1
lim = 10 ** 18


for i in range(len(A)):
    ans *= int(A[i])
if lim < ans and "0" not in A:
    print('-1')
else:
    print(ans)

# print(ans, lim)


### FIXED CODE ###

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

ans = 1
if 0 in a:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 1e18:
        break

if ans > 1e18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from collections import deque
N,M=map(int,input().split())
Table=[[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    Table[a-1].append(b-1)
    Table[b-1].append(a-1)
visit=[False]*N
iro=[-1]*N
kei=deque()
def nibu():
    kei.append(0)
    iro[0]=0
    while kei:
        x = kei.pop()
        visit[x]=True
        for i in Table[x]:
            if visit[i] and iro[i] == iro[x]:
                return False
            elif not visit[i]:
                kei.append(i)
                iro[i]=(iro[x]+1)%2
    return True
if nibu():
    B = iro.count(0)
    W = iro.count(1)
    ans = B*W-M
else:
    ans = (N*(N-1))//2 -M
print(ans)

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
Table=[[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    Table[a-1].append(b-1)
    Table[b-1].append(a-1)
visit=[False]*N
iro=[-1]*N
kei=deque()
def nibu():
    kei.append(0)
    iro[0]=0
    while kei:
        x = kei.pop()
        visit[x]=True
        for i in Table[x]:
            if visit[i] and iro[i] == iro[x]:
                return False
            elif not visit[i]:
                kei.append(i)
                iro[i]=(iro[x]+1)%2
    return True
if nibu():
    B = iro.count(0)
    W = iro.count(1)
    ans = B*W-M
else:
    ans = (N*(N-1))//2 -M
print(ans)
### BUGGY CODE ###

import itertools

#入力
N=int(input())
A = [int(x) for x in list(input())]
dict = {}

for i,j,k in itertools.combinations(A, 3):
    if(not((i,j,k) in dict)):
        dict[i,j,k]=1
#print(dict)
print(len(dict))

### FIXED CODE ###

# 入力
N = int(input())
A = [int(x) for x in list(input())]
ans = 0

AA = [x for x in range(10)]

for i in AA:
    for j in AA:
        for k in AA:
            v = [i, j, k]
            now=0
            temp=v[now]
            for l in A:
                if (l ==temp):
                    now += 1
                    if (now == 3):
                        # print(v)
                        break
                    temp = v[now]
            if (now == 3):
                ans += 1

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

n, q = map(int, input().split())

s = input()

for i in range(q):
    l, r  = map(int, input().split())
    temp = s[l-1:r]
    print(temp.count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())

s = input()

cnt = [0]

for i in range(1,len(s)+1):
    temp = s[i-1:i+1]
    # print(temp)
    if temp == 'AC':
        cnt.append(cnt[i-1] + 1)
    else:
        cnt.append(cnt[i-1])

# print(cnt)
for i in range(q):
    l, r  = map(int, input().split())
    print(cnt[r - 1] - cnt[l - 1])
### BUGGY CODE ###

h,w,m = map(int,input().split())
hw = [list(map(int,input().split()))for _ in range(m)]

tate = [0]*(h+1)
yoko = [0]*(w+1)

for x,y in hw:
    tate[x] += 1
    yoko[y] += 1

ans_x = set()
ans_y = set()
x_max = max(tate)
y_max = max(yoko)
for i in range(len(tate)):
    if tate[i] == x_max:
        ans_x.add(i)
for i in range(len(yoko)):
    if yoko[i] == y_max:
        ans_y.add(i)

ans = x_max + y_max
for x in ans_x:
    for y in ans_y:
        if [x,y] not in hw:
            print(ans)
            exit()
print(ans - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h,w,m = map(int,input().rstrip().split())
hw = [list(map(int,input().rstrip().split()))for _ in range(m)]

tate = [0]*(h+1)
yoko = [0]*(w+1)
bombpoint = set()

for x,y in hw:
    tate[x] += 1
    yoko[y] += 1
    bombpoint.add((x,y))

ans_x = []
ans_y = []
x_max = max(tate)
y_max = max(yoko)
for i in range(len(tate)):
    if tate[i] == x_max:
        ans_x.append(i)
for i in range(len(yoko)):
    if yoko[i] == y_max:
        ans_y.append(i)

ans = x_max + y_max
for x in ans_x:
    for y in ans_y:
        if (x,y) not in bombpoint:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
import collections

for i in A:
	if A.count(i)>1:
		cnt = 1
		break
if cnt == 0:
	print('YES')
else:
	print('NO')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
from collections import Counter
B=Counter(A)
C=B.most_common()
if C[0][1] <= 1:
	print('YES')
else:
	print('NO')
### BUGGY CODE ###

from collections import Counter as C

n  =  int(input())
a= list(input().split())
al = list([int(i) for i in a])
aset = set([int(i) for i in a])

cnt=0

#print(C(al)[0])
for i in aset:
  #print(i)
  #print(al.count(i-1),al.count(i),al.count(i+1))
  if cnt < C(al)[i-1] + C(al)[i] + C(al)[i+1]:
    cnt = C(al)[i-1] + C(al)[i] + C(al)[i+1]

print(cnt)

### FIXED CODE ###

from collections import Counter as C

n  =  int(input())
a= list(input().split())
al = list([int(i) for i in a])
aset = set([int(i) for i in a])

cnt=0
ca = C(al)
#print(C(al)[0])
for i in aset:
  #print(i)
  #print(al.count(i-1),al.count(i),al.count(i+1))
  if cnt < ca[i-1] + ca[i] + ca[i+1]:
    cnt = ca[i-1] + ca[i] + ca[i+1]

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

n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
L=len(format(max(a),"b"))
s=[0]*L
for i in range(n):
  c=format(a[i], 'b').zfill(L)
  for j in range(len(c))[::-1]:
    s[j]+=int(c[j])
ans=0
for i in range(len(s))[::-1]:
  add=(s[L-i-1])*(n-s[L-i-1])
  for j in range(i):
    add*=2
    add%=mod
  ans+=add
  ans%=mod
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
s=[0]*61
for i in range(n):
  c=format(a[i], 'b')
  L=len(c)
  for j in range(L)[::-1]:
    s[L-j-1]+=int(c[j])
ans=0
for i in range(61):
  ans+=2**(i)*(s[i])*(n-s[i])
  ans%=mod
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
p = 0
if n <= 2:
    if a[0] < a[1]:
        exit(print('Yes'))
    else:
        exit(print('No'))
p = 1
for i in range(k): p *= a[i]
for i in range(k,n):
    t = (p // a[i-k]) * a[i]
    if p < t:
        p = t
        print('Yes')
    else:
        p = t
        print('No')

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(k,n): print('Yes' if a[i] > a[i-k] else 'No')
### BUGGY CODE ###

import queue

N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
 
for i in range(N-1):
    a,b = map(int,input().split())
    Ki_p[b] = a
    Ki_c[a] += [b]
 
for i in range(Q):
    p,x = map(int,input().split())
    Ki_co[p] += x
 
ans = [0 for i in range(N+1)]
q = queue.Queue()
q.put(1)
while not q.empty():
    vi = q.get()
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    for a in Ki_c[vi]:
        q.put(a)
 
print(' '.join(map(str,ans[1:N+1])))

### FIXED CODE ###

N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
 
for i in range(N-1):
    a,b = map(int,input().split())
    Ki_p[b] = a
    Ki_c[a] += [b]
 
for i in range(Q):
    p,x = map(int,input().split())
    Ki_co[p] += x
 
ans = [0 for i in range(N+1)]
q = {1}
for i in range(N):
    vi = q.pop()
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    q |= set(Ki_c[vi])
    
print(' '.join(map(str,ans[1:N+1])))
### BUGGY CODE ###

from bisect import bisect_left

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

L.sort()

num_triangles = 0
for i in range(N-2): # stick 1
    for j in range(i+1, N-1): # stick 2; must be larger than 1
        # if a<b then we require c<b+a
        idx = bisect_left(a=L, x=L[i]+L[j], lo=j+1) # find the index at which c<b+a
        num_triangles += idx-(j+1) # c can be, at minimum, b=c
print(num_triangles)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

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

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)'''

n=int(input())
a=list(map(int, input().split()))
#print(sorted(a))
a.sort()
wa=[a[0]]
cnt=0
bl=[]
def ok(wa,item,cnt,bl):
    for j in range(len(wa)):
        if item%wa[j]==0:
            if item==wa[j]:
                bl.append(item)
                return
            else:
                return
    wa.append(item)
    #print(item,wa,cnt)
    return

for item in a[1:]:
    ok(wa,item,cnt,bl)
    #print(cnt)

print(max(0,len(wa)-len(set(bl))))

### FIXED CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
def cal(n,li):
    lis=[True]*(n+1)
    for item in li:
        if lis[item]:
            for i in range(item*2,n+1,item):
                lis[i]=False
    return lis
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=cal(a[-1],a)
ll=Counter(a)
#print(l,ll)
ans=0
for i in range(n):
    if ll[a[i]]==1:
        if l[a[i]]:
            ans+=1

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

def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)


### FIXED CODE ###

def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)
### BUGGY CODE ###

import math

def Combination(n, r):
	if n >= r:
		return math.factorial(n) // (r * math.factorial(n - r))
	else:
		return 0

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

cnt = [0] * N
for i in A:
	cnt[i - 1] += 1

cmb = [0] * N
for i in range(N):
	cmb[i] = Combination(cnt[i], 2)

asum = sum(cmb)
for i in A:
	print(asum - cmb[i - 1] + Combination(cnt[i - 1] - 1, 2))

### FIXED CODE ###

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

cnt = [0] * N
for i in range(N):
	cnt[A[i] - 1] += 1

cmbr2 = [0] * (N + 1)
for i in range(1, N + 1):
	cmbr2[i] = cmbr2[i - 1] + i - 1

cmb = [0] * N
for i in range(N):
	cmb[i] = cmbr2[cnt[i]]

asum = sum(cmb)
for i in A:
	print(asum - cmbr2[cnt[i - 1]] + cmbr2[cnt[i - 1] - 1])
### BUGGY CODE ###

from  operator import itemgetter

# 満足ポイントを求める関数
def f(a, b):
    return len(a) ** 2 + sum(a) + sum(b)

n, k = map(int, input().split())

sushi = []
for i in range(n):
    sushi.append(list(map(int, input().split())))

sushi.sort(key=itemgetter(1), reverse=True)

s = []
s_change = []
types = []
# 集合Sの生成
for i in range(k):
    if sushi[i][0] not in types:
        s.append(sushi[i])
        types.append(sushi[i][0])
    else:
        s_change.append(sushi[i])

s_change.sort(key=itemgetter(1))
#print(s)
#print(s_change)

m = []
# 交換用の集合の生成
for i in range(k, n):
    if sushi[i][0] not in types:
        m.append(sushi[i])
        types.append(sushi[i][0])

#print(m)
#print([l[1] for l in s])
g = []
g.append(f([l[1] for l in s], [l[1] for l in s_change]))

# 集合gを求める
for i in range(min(len(s_change), len(m))):
    s.append(m[i])
    s_change.pop(0)
    g.append(f([l[1] for l in s], [l[1] for l in s_change]))

print(max(g))



### FIXED CODE ###

# 入力
n, k = map(int, input().split())
A = [] # 寿司のネタの美味しさと種類を入れるリスト
for _ in range(n):
    A.append(list(map(int, input().split())))

# 美味しさ順にソートする
A.sort(key=lambda x: x[1], reverse=True)

# 美味しさで貪欲にとる
X = [] # 同じ種類で他に美味しさの大きい寿司が存在する
Y = [] # 取った寿司の中の各々の種類で美味しさが最も大きい
st = set() # 種類
for i in range(k):
    t, d = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)

# 美味しさポイントを求める
x = sum(X)
y = sum(Y)
v = len(Y) # 種類数
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    t, d = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)

print(ans)