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

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
flag = np.zeros(N, dtype=int)

ans = 0
for i in range(N-1, -1, -1):
    if flag[i]:
        continue
    if A_list[idx[i]] == cand_A[i]:
        cand_idx = idx[i]
        while (cand_idx < i) and (A_list[cand_idx] == cand_A[i]):
            if not flag[cand_idx]:
                ans += 1
                flag[cand_idx] = 1
                break
            cand_idx += 1

print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
from collections import Counter

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
A_count = dict(Counter(A_list))

ans = 0
for i in range(N-1, -1, -1):
    if A_count[A_list[i]] <= 0:
        continue
    A_count[A_list[i]] -= 1
    if (A_list[idx[i]] == cand_A[i]) and (A_count[cand_A[i]] > 0):
        ans += 1
        A_count[cand_A[i]] -= 1

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

def check_all_distinct(A):
  for idx, character in enumerate(A):
    if character in A[idx+1:]: return "NO"
  return "YES"


if __name__ == "__main__":
  N = int(input())
  A = input().split()
  dict_chars = dict()
  print(check_all_distinct(A))

### FIXED CODE ###

N = int(input())
A = input().split()
if len(A) != len(set(A)):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 10**9 + 7
k = int(input())
s = input()
n = len(s)

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(10**7)
ans = 0
for i in range(k + 1):
    temp = 1
    temp *= pow(26, i, mod)
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= pow(25, j, mod)
    temp %= mod
    temp *= nCk(n + j - 1, n - 1)
    ans += temp
    ans %= mod
print(ans)





### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 10**9 + 7
k = int(input())
s = input()
n = len(s)

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(2*10**6 + 1)
ans = 0
for i in range(k + 1):
    temp = 1
    temp *= pow(26, i, mod)
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= pow(25, j, mod)
    temp %= mod
    temp *= nCk(n + j - 1, n - 1)
    ans += temp
    ans %= mod
print(ans % mod)
### BUGGY CODE ###

# coding: utf-8
a,b,c,k = map(int, input().split())
sum = 0
if b == 0 and c == 0:
    print(k)
else:
    for i in range(k):
        if a > 0:
           sum = sum + 1
           a = a - 1
        elif b > 0:
            b = b - 1
        elif c > 0:
            sum = sum - 1
            c = c - 1
    print(sum)

### FIXED CODE ###

# coding: utf-8
import sys
# sys.exit()
a,b,c,k = map(int, input().split())
# sum = 0
if k <= a:
    sum = k
    print(sum)
    sys.exit()
else:
    sum = a
    k = k - a
if k <= b:
    print(sum)
    sys.exit()
else:
    k = k - b
    sum = sum - k
    print(sum)
### BUGGY CODE ###

def dfs(item_i, W):
    if item_i >= N:
        return 0
    if visited[item_i][W]:
        return table[item_i][W]
    visited[item_i][W] = True
    if W - w_list[item_i] < 0:
        table[item_i][W] = dfs(item_i+1, W)
    else:
        table[item_i][W] = max(dfs(item_i+1, W), dfs(item_i+1, W-w_list[item_i]) + v_list[item_i])
    
    return table[item_i][W]

N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
table = [[0 for j in range(W+1)]for i in range(N)]
visited = [[False for j in range(W+1)]for i in range(N)]

ans = dfs(0, W)
print(ans)

### FIXED CODE ###

N, maxW = map(int, input().split())
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))
### BUGGY CODE ###

n = int(input())
num = [int(input()) for _ in range(n)]
ans = 0

for i in set(num):
    if num.count(i)%2 == 1:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
a = sorted([int(input()) for _ in range(n)])
ans = 0
count = 0
pre = a[0]

for i in range(n):
    if a[i] == pre:
        count+=1
    else:
        pre = a[i]
        if count%2 == 1:
            ans += 1
        count = 1
if count%2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

X = input().split()
N = int(X[0])
K = int(X[1])

while N > K:
    N = abs(N - K)
N1 = abs(N - K)
if N > N1:
    print(N1)
else:
    print(N)

### FIXED CODE ###

X = input().split()
N = int(X[0])
K = int(X[1])

N = N % K
N1 = abs(N - K)
if N > N1:
    print(N1)
else:
    print(N)
### BUGGY CODE ###

from collections import deque
N,M,K=map(int,input().split())
F,B=[[] for _ in range(N)],[[] for _ in range(N)]
for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  F[a].append(b)
  F[b].append(a)
for _ in range(K):
  c,d = map(int,input().split())
  c,d=c-1,d-1
  B[c].append(d)
  B[d].append(c)
#print(F,B)
C=[[] for _ in range(N)]
finished = []
for i,f in enumerate(F):
  if i in finished: continue
  store = deque([i])
  c = []
  while len(store)>0:
    s = store.popleft()
    if s in c:continue
    c.append(s)
    store.extend(F[s])
  finished.extend(c)
  for c2 in c:
    C[c2] = [v for v in c if v!=c2 and v not in F[c2] and v not in B[c2]]
#print(F,B,C)
print(' '.join([str(len(v)) for v in C]))

### FIXED CODE ###

from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    
def dfs(v, temp):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(i, temp)
    return temp
visited = [False]*n

cc = [0]*n
for v in range(n):
    if visited[v] == False:
        c = dfs(v,set())
        for i in c:
            cc[i] = c


ans = []
for i in range(n):
    aa = len(cc[i]) - len(cc[i] & fr[i]) - len(cc[i] & bl[i]) - 1
    ans.append(aa)
print(*ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
            break
    if flag:
        continue
    else:
        bridge[q-1]=1
        cnt+=1
print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

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

import math

a, b, n = map(int, input().split())
y = 0
lst = []
for i in range(1, n+1):
    y = math.floor(a*i/b) - a * math.floor(i/b)
    lst.append(y)

print(max(lst))


### FIXED CODE ###

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

x = 0
ans = 0
if n < b:
    x = n
    ans = math.floor(a*x/b) - a * math.floor(x/b)
else:
    x = b - 1
    ans = math.floor(a*x/b) - a * math.floor(x/b)
print(ans)
### BUGGY CODE ###

#A,B,C,D=map(int,input().split(" "))

mod=2019
a=input()

N=len(a)
t=[]
ans=0

for i in range(N):
  for j in range(i+1,N+1):
    u=int(a[i:j])
    #print(u)
    if (u % mod)==0:
      ans+=1
      #print(i+1,j)
      break
print(ans)


### FIXED CODE ###

mod=2019
a=input()

N=len(a)
t=[0]*mod
t[0]=1

w=1
u=0

for i in range(N):
  u=int(a[N-1-i]) * w + u
  v=u % mod
  t[v] += 1
  w *=10
  w %= mod

ans=0
for i in t:
  ans += (i-1)*i//2

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

x, y = map(int, input().split())
count = 0
while x > 2 or y > 2:
    if (x % 2 == 1 and y % 2  == 1) or (x % 2 == 0 and y % 2  == 0)  : 
    
        if x >= y:
            a = (x / 2) * 2
            x -= a
            y += a / 2
            count += 1
    
        else:
            a = (y / 2) * 2
            y -= a
            x += a / 2
            count += 1
    elif x % 2 == 0:
        a = (x / 2) * 2
        x -= a
        y += a / 2
        count += 1
    elif y % 2 == 0:
        a = (y / 2) * 2
        y -= a
        x += a / 2
        count += 1
        
        

if count % 2 == 0:
    print("Brown")
else:
    print("Alice")

### FIXED CODE ###

x, y = map(int, input().split())
if abs(x-y)<=1:
    print("Brown")
else:
    print("Alice")
### BUGGY CODE ###

N = int(input())
s = []
temp = []
for i in range(N):
    s.append(sorted(list(input())))
    temp.append(i)

ans = 0
for i in temp:
    for j in temp:
        if not i == j:
            if (s[i] == s[j]):
                ans += 1
print(int(ans/2))

### FIXED CODE ###

N = int(input())
s = []
ans = 0
mydict = {}
for i in range(N):
    s = "".join(sorted(list(input())))
    if (s in mydict.keys()):
        ans += mydict[s]
        mydict[s] += 1
    else:
        mydict[s] = 1
print(ans)
### BUGGY CODE ###

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

for i in range(M):
    ind = A.index(max(A))
    A[ind] = A[ind]//2

print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N):
    A[i] = -A[i]
heapq.heapify(A)

for i in range(M):
    trgt = -heapq.heappop(A)//2
    heapq.heappush(A,-trgt)
print(-sum(A))
### BUGGY CODE ###

N = int(input())
ls = []
cnt = []

for _ in range(N):
  S = input()
  if S in ls:
    cnt[ls.index(S)] += 1
    continue
  
  ls.append(S)
  cnt.append(1)
  
max_cnt = max(cnt)

res = []
for i,j in zip(ls,cnt):
  if j == max_cnt:
    res.append(i)
    
res.sort()
for ans in res:
  print(ans)

### FIXED CODE ###

N = int(input())
index = {}

for _ in range(N):
  S = input()
  if S not in index: index[S] = 1
  else: index[S] += 1

max_cnt = max(index.values())

ls = [key for key in index.keys() if index[key] == max_cnt]

ls.sort()
for ans in ls:
  print(ans)
### BUGGY CODE ###

import fractions

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

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

box = cf(A,B)
box = sorted(box)

tmp = []

for l in range(len(box)-1):
  for m in range((l+1),len(box)):
    if fractions.gcd(box[l],box[m]) != 1:
      tmp.append(box[m])
      
print(len(box)-len(set(tmp))+1)

### FIXED CODE ###

#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)
hoge = []
if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

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

import math

k = int(input())

ans = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1,k+1):
            ans += math.gcd(a, math.gcd(b, c))

print(ans)


### FIXED CODE ###

ans = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
print(ans[int(input())-1])
### BUGGY CODE ###

import sys
import math
K = int(input())
A = [int(x) for x in input().split()]
A.reverse()
jmax, jmin = 2,2

if A[0] != 2:
    print(-1)
    sys.exit()

for i in range(0,K):  # 0<=i<=K-2 A[K-2]は2ラウンドの組．Kラウンドから2ラウンドまで
    Round = list(range(jmin,jmax+1))
    decide = [Round[h] % A[i] for h in range(len(Round))]
    if not(0 in decide):
        print(-1)
        sys.exit()
    jmin = (math.ceil(jmin / A[i])) * A[i]
    jmax = (math.floor(jmax / A[i])) * A[i] + A[i] -1

print(jmin, jmax)


### FIXED CODE ###

from math import floor,ceil
K = int(input())
A = [int(x) for x in input().split()]
A.reverse()
jmax, jmin = 2,2

for i in range(0,K):
    mmax,mmin = jmax,jmin
    if mmin % A[i] != 0:
        if (mmin + (A[i] - (mmin % A[i]))) > mmax:
            print(-1)
            exit()

    jmin = ceil(jmin / A[i]) * A[i]
    jmax = floor(jmax / A[i]) * A[i] + A[i] -1

print(jmin, jmax)

#計算量はO(3K)すなわちO(K)
### BUGGY CODE ###

n = int(input())

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


checked = []
ans = 0
for i in a:
  if i not in checked:
    #多すぎる場合はその数になるまで取り除く
    if a.count(i) >= i:
      ans += a.count(i) - i
    else:
      #その値以下の数しかないので配列から取り除く
      ans += a.count(i)
    checked.append(i) 
print(ans)

### FIXED CODE ###

n = int(input())

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


checked = []
ans = 0
cnt_a = {}
for i in a:
  if i in cnt_a:
    cnt_a[i] += 1
  else:
    cnt_a[i] = 1

for k in cnt_a.keys():
  if cnt_a[k] >= k:
    ans += cnt_a[k] - k
  else:
    ans += cnt_a[k]
    
print(ans)
### BUGGY CODE ###

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

l.sort()
l.reverse()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i]<l[j]+l[k]:
                ans+=1
            else:
                break

print(ans)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)
 
print(ans)
### BUGGY CODE ###

N = int(input())
S = str(input())


R = 0
G = 0
B = 0

for i in range(N):
    s = S[i]
    if (s == 'R'):
        R +=1
    if (s == 'G'):
        G +=1
    if (s == 'B'):
        B +=1

count = R * G * B


for i in range(N):
    for j in range(N//2 + 1):
        if(i + j*2 >= N):
            break
        if((S[i] != S[i + j]) & (S[i + j] != S[i + 2 * j]) & (S[i + 2 * j] != S[i])):
            count -= 1




print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[[0]*n*2for _ in range(26)]
  def update(i,x):
    i+=n
    for d in data:
      j=i
      if d[j]:
        d[j]=0
        j//=2
        while j:
          d[j]=d[j+j]|d[j-~j]
          j//=2
        break
    d=data[x]
    d[i]=1
    i//=2
    while i:
      d[i]=d[i+i]|d[i-~i]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=[0]*26
    while l<r:
      if l&1:
        for i,d in enumerate(data):
          s[i]|=d[l]
        l+=1
      if r&1:
        r-=1
        for i,d in enumerate(data):
          s[i]|=d[r]
      l//=2
      r//=2
    return sum(s)
  for i,c in enumerate(input()[:-1]):
    update(i,c-97)
  s=[]
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:
      s+=query(int(a)-1,int(b)),
    else:
      update(int(a)-1,b[0]-97)
  print('\n'.join(map(str,s)))
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
pi = np.array(list(map(int, input().split())))
index = []
for i in range(N-K+1):
    x = sum(pi[i:i+K])
    index.append(x)
max_index = index.index(max(index))
array_max = (np.array(pi[max_index:max_index+K])-1) *0.5 + 1
print(array_max.sum())

### FIXED CODE ###

N, K = map(int, input().split())
pi = list(map(int,input().split()))
def EV(x):
    return 1+(x-1)*0.5
for i in range(N):
    pi[i] = EV(pi[i])

ruisekiwa = sum(pi[0:K])
max_EV = ruisekiwa

for i in range(N-K):
    ruisekiwa = ruisekiwa + pi[i+K]-pi[i]
    if ruisekiwa > max_EV:
        max_EV = ruisekiwa
print(max_EV)
### BUGGY CODE ###

from collections import Counter
N, K =  map(int, (input().split(' ')))
sushi = [tuple(map(int, input().split(' '))) for _ in range(N)]
all_sushi = sorted(sushi, key=lambda x: -x[1])
default_sushi = all_sushi[:K]
amari = all_sushi[K:]
counter = Counter([i[0] for i in default_sushi])
result = []
def calc_value(sushi):
    return sum([i[1] for i in sushi]) + len(counter)**2

fs = []
def change_sushi(sushi):
    oishisa = sum([i[1] for i in sushi])
    fs.append(oishisa + len(counter)**2)
    amari_index = 0
    for s in sushi[::-1]:
        if counter[s[0]] >= 2:
            for i, a in enumerate(amari[amari_index:], start=1):
                if a[0] not in counter:
                    counter[s[0]] -= 1
                    counter[a[0]] += 1
                    oishisa = oishisa - s[1] + a[1]
                    #amari = amari[:i] + amari[i+1:]
                    #sushi = [a] + sushi[:-1]
                    #return sushi
                    fs.append(oishisa + len(counter)**2)
                    amari_index = amari_index + i
                    
                    break
    print(max(fs))
    exit()
            
    
def get_sushi(sushi):
    #result.append(calc_value(sushi))
    changed_sushi = change_sushi(sushi)
    #if not changed_sushi:
        #print(max(result))
        #return
    #get_sushi(changed_sushi)

get_sushi(default_sushi)


### FIXED CODE ###

from collections import Counter
N, K =  map(int, (input().split(' ')))
sushi = [tuple(map(int, input().split(' '))) for _ in range(N)]
all_sushi = sorted(sushi, key=lambda x: -x[1])
default_sushi = all_sushi[:K]
amari = all_sushi[K:]
len_amari = len(amari)
counter = Counter([i[0] for i in default_sushi])
result = []
def calc_value(sushi):
    return sum([i[1] for i in sushi]) + len(counter)**2

fs = []
def change_sushi(sushi):
    oishisa = sum([i[1] for i in sushi])
    fs.append(oishisa + len(counter)**2)
    amari_index = 0
    for s in sushi[::-1]:
        if counter[s[0]] >= 2:
            while amari_index < len_amari:
                a = amari[amari_index]
                amari_index += 1
                if a[0] not in counter:
                    counter[s[0]] -= 1
                    counter[a[0]] += 1
                    oishisa = oishisa - s[1] + a[1]
                    fs.append(oishisa + len(counter)**2)
                    break
    print(max(fs))
    exit()
            
    
def get_sushi(sushi):
    #result.append(calc_value(sushi))
    changed_sushi = change_sushi(sushi)
    #if not changed_sushi:
        #print(max(result))
        #return
    #get_sushi(changed_sushi)

get_sushi(default_sushi)