CodeEff/ECCO huggingface dataset:
# Original solution
import queue
dic = {
        'rg':'b', 'gr':'b',
        'gb':'r', 'bg':'r',
        'br':'g', 'rb':'g',
        }
while True:
    s = input()
    if s=='0':
        break
    que = queue.PriorityQueue()
    l = len(s)
    cost = {}
    cost[s] = 0
    que.put((0, s))
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if all(e == ss[0] for e in ss):
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in range(l-1):
            cc = ss[i:i+2]
            if cc[0]!=cc[1]:
                code = dic[cc]
                sa = ss[:i] + code*2 + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print("NA" if ans<0 else ans)

# Optimized solution
import queue
dic = {
        'rg':'bb', 'gr':'bb',
        'gb':'rr', 'bg':'rr',
        'br':'gg', 'rb':'gg',
        }
while True:
    s = input()
    if s=='0':
        break
    que = queue.PriorityQueue()
    l = len(s)
    cost = {s: 0}
    que.put((0, s))
    aa = ['r'*l, 'g'*l, 'b'*l]
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if ss in aa:
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in range(l-1):
            cc = ss[i:i+2]
            if cc[0]!=cc[1]:
                sa = ss[:i] + dic[cc] + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print("NA" if ans<0 else ans)
# Original solution
rgb = set(["r","g","b"])
while 1:
	worm = input()
	if worm == "0": break
	n = len(worm)
	que = [worm]
	ref = set(worm)
	L = 1
	cnt = flag = 0
	while 1:
		for r in range(L):
			Worm = que.pop(0)
			if Worm in ref: continue
			else: ref.add(Worm)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					worm = Worm[:]
					nextclr = list(rgb-set(worm[i:i+2]))[0]
					worm = worm[:i] + 2*nextclr + worm[i+2:]
					if worm not in que: que.append(worm)
		L = len(que)
		if flag or L == 0: break
		cnt += 1
		if cnt > 15: break
	print(cnt if flag else "NA")

# Optimized solution
rgb = set(["r","g","b"])
while 1:
	worm = input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	while 1:
		que = list(queset)
		queset = set()
		for r in range(L):
			Worm = que.pop(0)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 15: break
	print(cnt if flag else "NA")
# Original solution
rgb = set(["r","g","b"])
while 1:
	worm = input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	while 1:
		que = list(queset)
		queset = set()
		for r in range(L):
			Worm = que.pop(0)
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 15: break
	print(cnt if flag else "NA")

# Optimized solution
rgb = set(["r","g","b"])
while 1:
	worm = input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	ref = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		queset = queset - ref
		ref = ref|queset
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 15: break
	print(cnt if flag else "NA")
# Original solution
rgb = set(["r","g","b"])
while 1:
	worm = input()
	if worm == "0": break
	n = len(worm)
	L = 1
	cnt = flag = 0
	queset = set([worm])
	ref = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if len(set(Worm)) == 1:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = list(rgb-set(Worm[i:i+2]))[0]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					queset.add(worm)
		queset = queset - ref
		ref = ref|queset
		L = len(queset)
		if flag: break
		cnt += 1
		if cnt > 15: break
	print(cnt if flag else "NA")

# Optimized solution
dic = {"r":1,"g":2,"b":3}
rgb = ["r","g","b"]
while 1:
	worm = input()
	if worm == "0": break
	n = len(worm)
	ref = ["r"*n,"g"*n,"b"*n]
	cnt = flag = 0
	queset = set([worm])
	done = set()
	while 1:
		que = list(queset)
		queset = set()
		for Worm in que:
			if Worm in ref:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = rgb[5-dic[Worm[i]]-dic[Worm[i+1]]]
					queset.add(Worm[:i] + 2*nextclr + Worm[i+2:])
		if flag or cnt > 14: break
		cnt += 1
		queset -= done
		done |= queset
	print(cnt if flag else "NA")
# Original solution
from statistics import mean

inputCount = int(eval(input()))
prices = [int(eval(input())) for lp in range(inputCount)]
average = mean(prices)
print((int(average)))



# Optimized solution
inputCount = int(eval(input()))
prices = [int(eval(input())) for lp in range(inputCount)]
average = sum(prices) // inputCount
print(average)
# Original solution
N,X=list(map(int,input().split()))
L=sorted(map(int,input().split()),reverse=True)
mod=10**9+7

from collections import defaultdict
D=defaultdict(int)
D[1,L[0]]=1

for l in L[1:]:
    ND=defaultdict(int)

    for c,s in D:
        k=D[c,s]

        if s+l+c-1<=X:
            ND[c+1,s+l]=(ND[c+1,s+l]+k*(c+1))%mod
        ND[c,s]=(ND[c,s]+k*(s-c*(l-1)))%mod

        for i in range(1,min(X-s-c+2,l+1)):
            ND[c,s+i]=(ND[c,s+i]+k*2*c)%mod

        for i in range(1,min(X-s-c+3,l+1)):
            ND[c-1,s+i]=(ND[c-1,s+i]+k*(c-1)*(l-i+1))%mod
    D=ND

print((D[1,X]))

# Optimized solution
N,X=list(map(int,input().split()))
L=sorted(map(int,input().split()),reverse=True)
mod=10**9+7

D=[[0]*(X+1) for i in range(N//2+2)]
D[1][L[0]]=1

for l in L[1:]:
    ND=[[0]*(X+1) for i in range(N//2+1)]

    for c in range(1,N//2+1):
        for s in range(X+1):
            if D[c][s]==0:
                continue
            
            k=D[c][s]

            if s+l+c<=X and c+1<=N//2:
                ND[c+1][s+l]=(ND[c+1][s+l]+k*(c+1))%mod
            ND[c][s]=(ND[c][s]+k*(s-c*(l-1)))%mod

            for i in range(1,min(X-s-c+2,l+1)):
                ND[c][s+i]=(ND[c][s+i]+k*2*c)%mod

            if c==1:
                continue

            for i in range(1,min(X-s-c+3,l+1)):
                ND[c-1][s+i]=(ND[c-1][s+i]+k*(c-1)*(l-i+1))%mod
    D=ND

print((D[1][X]))
# Original solution
while 1:
    a=[i+1 for i in range(10)]
    try:b=list(map(int,input().split()))
    except:break
    for i in b:a.remove(i)
    print((['NO','YES'][sum([1 for i in a if sum(b[:2],i)<=20])/7>=0.5]))

# Optimized solution
while 1:
    a=[i+1 for i in range(10)]
    try:b=list(map(int,input().split()))
    except:break
    for i in b:a.remove(i)
    c=sum(b[:2])
    print((['NO','YES'][sum([1 for i in a if c+i<=20])/7>=0.5]))
# Original solution
import sys
for s in sys.stdin:
    C=[0]+[1]*10
    a,b,c=list(map(int,s.split()))
    C[a]=0
    C[b]=0
    C[c]=0
    if sum(C[:21-a-b])>=4:print("YES")
    else: print("NO")

# Optimized solution
import sys
for s in sys.stdin:
    a,b,c=list(map(int,s.split()))
    x=20-a-b
    f=3
    if x<a: f-=1
    if x<b: f-=1
    if x<c: f-=1
    if x-f>=4:print("YES")
    else: print("NO")
# Original solution
N,K=list(map(int,input().split()))

td=sorted([tuple(map(int,input().split())) for _ in range(N)],key=lambda x:-x[1])
answer=0
number=[]
afterpop=[]

for i in range(K):
  answer+=td[i][1]
  if td[i][0] not in number:
    number.append(td[i][0])
  else:
    afterpop.append(td[i][1])

answer+=len(number)**2
    
index=K
tempanswer=answer
while index<N and afterpop:
  if td[index][0] not in number:
    number.append(td[index][0])
    tempanswer=tempanswer+td[index][1]-afterpop.pop()-(len(number)-1)**2+(len(number))**2
    answer=max(tempanswer,answer)
  index+=1
                  
print(answer)

# Optimized solution
N,K=list(map(int,input().split()))

td=sorted([tuple(map(int,input().split())) for _ in range(N)],key=lambda x:-x[1])
answer=0
number=set()
afterpop=[]

for i in range(K):
  answer+=td[i][1]
  if td[i][0] not in number:
    number.add(td[i][0])
  else:
    afterpop.append(td[i][1])

answer+=(len(number))**2
    
index=K
tempanswer=answer
while index<N and afterpop:
  if td[index][0] not in number:
    number.add(td[index][0])
    tempanswer=tempanswer+td[index][1]-afterpop.pop()-(len(number)-1)**2+(len(number))**2
    answer=max(tempanswer,answer)
  index+=1
                  
print(answer)
# Original solution
N,K=list(map(int,input().split()))

l=[] # 寿司リスト。ただし，「おいしさ」を第1要素にする
dj=[] # 寿司タプルをそのまま入れる
s=set()

for i in range(N):
    t,d=list(map(int,input().split()))
    l.append((d,t))
l.sort(reverse=True) 

ans=K**2
j=0 # 既に食べたことのある種類の寿司を更に食べた回数

for i in range(K): # i番目に食べる寿司について
    while l and l[0][1] in s:
        dj.append(l.pop(0))
    if (l and dj and l[0][0]>=dj[0][0]-(2*K-1-2*j)) or not dj:
        ans+=l[0][0]
        s.add(l[0][1])
        l.pop(0)
    else:
        ans+=dj[0][0]-(2*K-1-2*j)
        dj.pop(0)
        j+=1

print(ans)

# Optimized solution
N,K=list(map(int,input().split()))

l=[] # 寿司リスト。ただし，「おいしさ」を第1要素にする
m=[] # 寿司タプルをそのまま入れる
s=set()

for i in range(N):
    t,d=list(map(int,input().split()))
    l.append((d,t))
l.sort(reverse=True) 

ans=K**2
t=0 # 既に食べたことのある種類の寿司を更に食べた回数

i=0 # l内を走査する際の添字
j=0 # m内を操作する際の添え字

for _ in range(K): # _番目に食べる寿司について
    while i<N and l[i][1] in s:
        m.append(l[i]) # そのままmに追加する
        i+=1 # lの先頭の要素を削除せず，
    if (i<N and (m and j<len(m)) and l[i][0]>=m[j][0]-(2*K-1-2*t)) or (not m or j>=len(m)):
        ans+=l[i][0]
        s.add(l[i][1])
        i+=1
    else:
        ans+=m[j][0]-(2*K-1-2*t)
        j+=1
        t+=1

print(ans)
# Original solution
from heapq import heappop, heappush
from collections import defaultdict

N, K = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N)]

# Step 1: Choose greedy
X.sort(key=lambda x: -x[1])
pq = []
chosen = defaultdict(int)
cnt = 0
score = 0
for t, d in X[:K]:
    heappush(pq, (d, t))
    cnt += 1 if chosen[t] == 0 else 0
    chosen[t] += 1
    score += d
ans = score + cnt ** 2

# Step 2: Replace chosen items
idx = K
while pq:
    # Step 2.1
    d_p, t_p = heappop(pq)
    if chosen[t_p] <= 1:
        continue
    chosen[t_p] -= 1
    score -= d_p

    # Step 2.2
    while idx < N and chosen[X[idx][0]] != 0:
        idx += 1

    if idx == N:
        break
        
    cnt += 1
    chosen[X[idx][0]] += 1
    score += X[idx][1]
    ans = max(ans, score + cnt ** 2)
    
print(ans)



# Optimized solution

from collections import defaultdict
from heapq import heappop, heappush

N, K = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N)]

X.sort(key=lambda x: x[1])
pq = []
f_x = 0
ctr = defaultdict(int)
appeared = 0
for _ in range(K):
    t, d = X.pop()
    heappush(pq, (d, t))
    appeared += int(ctr[t] == 0)
    f_x += d
    ctr[t] += 1

res = f_x + appeared ** 2
while pq or X:
    while pq:
        d, t = heappop(pq)
        if ctr[t] > 1:
            ctr[t] -= 1
            f_x -= d
            break

    if not pq:
        break

    while X:
        t_x, d_x = X.pop()
        if ctr[t_x] == 0:
            heappush(pq, (d_x, t_x))
            f_x += d_x
            ctr[t_x] += 1
            appeared += 1
            res = max(res, f_x + appeared ** 2)
            break

print(res)
# Original solution
import itertools

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

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

# 貪欲で

td_comb = list(itertools.combinations(td, k))

ans = 0

for i in td_comb:
    tmp_ans = 0
    cnt = 0
    t_lst = []
    for j in i:
        tmp_ans += j[1]
        if j[0] not in t_lst:
            cnt += 1
            t_lst.append(j[0])
    tmp_ans += cnt**2
    ans = tmp_ans if tmp_ans>ans else ans

print(ans)

# Optimized solution
N, K = list(map( int, input().split()))
T = [(0,0)]*N
for i in range(N):
    t, d = list(map( int, input().split()))
    T[i] = (d,t)
T.sort( key= None, reverse = True)
C = T[:K]
AC = T[K:]
kiso = 0
s = 0
S = [0]*(N+1)
for i in range(K):
    d, t = T[i]
    kiso += d
    if S[t] == 0:
        S[t] = 1
        s += 1
    else:
        S[t] += 1
ans = kiso + s**2
C.sort()
r = 0
 
for i in range(K):
    d, t = C[i]
    if S[t] >= 2:
        while r < N-K:
            if S[ AC[r][1]] == 0:
                S[t] -= 1
                S[ AC[r][1]] += 1
                s += 1
                kiso -= d
                kiso += AC[r][0]
                r += 1
                break
            r += 1
    ans = max( ans, kiso + s**2)
print( ans)
# Original solution
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
dt = []
for i in range(n):
    t,d = inm()
    dt.append((d,t))
dt.sort(reverse=True)
a = dt[:k] # oisisa max, ignore variety

vals = [z[0] for z in a]
dsum = sum(vals)
typs = set([z[1] for z in a])
ntyp = len(typs)
mx = dsum+ntyp**2 # satisfy for a

b = dt[k:]
h = {}
for d,t in b:
    if t in typs:
        continue
    elif t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
c = [h[t] for t in h]
c.sort(reverse=True)
# for types not in a, max oisisa

h = {}
for d,t in a:
    if t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
for t in h:
    vals.remove(h[t])
vals.sort()
# oisisa list for second or below for each type

for i in range(min(len(vals),len(c))):
    dsum += c[i]-vals[i]
    ntyp += 1
    mx = max(mx,dsum+ntyp**2)
print(mx)


# Optimized solution
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
dt = []
for i in range(n):
    t,d = inm()
    dt.append((d,t))
dt.sort(reverse=True)
a = dt[:k] # oisisa max, ignore variety

vals = [z[0] for z in a]
dsum = sum(vals)
typs = set([z[1] for z in a])
ntyp = len(typs)
mx = dsum+ntyp**2 # satisfy for a

b = dt[k:]
h = {}
for d,t in b:
    if t in typs:
        continue
    elif t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
c = [h[t] for t in h]
c.sort(reverse=True)
# for types not in a, max oisisa

h = {}
for d,t in a:
    if t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
vals = []
for d,t in a:
    if t in h and d==h[t]:
        del h[t]
    else:
        vals.append(d)
vals.sort()
# oisisa list for second or below for each type

for i in range(min(len(vals),len(c))):
    dsum += c[i]-vals[i]
    ntyp += 1
    mx = max(mx,dsum+ntyp**2)
print(mx)
# Original solution
N, K = list(map(int, input().split()))
sushi = []
for i in range(N):
    s = list(map(int, input().split()))
    sushi.append(s)


sushi.sort(key=lambda x: x[1], reverse=True)

def find_next(start, curr, point, tlist, tcount):
    if start == N:
        return [point, curr]
    max_c = curr
    max_p = point
    for s in sushi[start:]:
        if tlist[s[0]] > 0:
            continue
        for ri in range(len(curr) - 1, -1, -1):
            r = curr[ri]
            if tlist[r[0]] >= 2:
                c2 = [c for c in curr]
                t2 = [t for t in tlist]
                del c2[ri]
                c2.append(s)
                t2[r[0]] -= 1
                t2[s[0]] = 1
                p2 = point - r[1] + s[1] + (tcount + 1) * (tcount + 1) - tcount * tcount
                np, pc = find_next(start + 1, c2, p2, t2, tcount + 1)

                if np > max_p:
                    max_p = np
                    max_c = pc
                return [max_p, max_c]
    return [max_p, max_c]

result = sushi[0: K]
type_count = [0] * (N + 1)

for r in result:
    type_count[r[0]] += 1
type_num = 0
for t in type_count:
    if t > 0:
        type_num += 1
point = type_num * type_num
for r in result:
    point += r[1]
ans_p, ans_c = find_next(K, result, point, type_count, type_num)

print(ans_p)

# Optimized solution
N, K = list(map(int, input().split()))
sushi = []
for i in range(N):
    s = list(map(int, input().split()))
    sushi.append(s)


sushi.sort(key=lambda x: x[1], reverse=True)

# pick from first
point = 0
neta_set = set()
removable_idx = list()
for i in range(K):
    s = sushi[i]
    point += s[1]
    if s[0] not in neta_set:
        neta_set.add(s[0])
    else:
        removable_idx.append(i)
point += len(neta_set) **2
max_point = point

# pick latest
for s in sushi[K:]:
    if len(removable_idx) == 0:
        break
    if s[0] in neta_set:
        continue
    idx = removable_idx[-1]
    count = len(neta_set)
    point += s[1] - sushi[idx][1]
    point += (count + 1) ** 2 - count ** 2
    neta_set.add(s[0])
    removable_idx = removable_idx[:-1]

    if point > max_point:
        max_point = point
print(max_point)
# Original solution
# D - Various Sushi
import sys
from collections import defaultdict
import heapq

readline = sys.stdin.readline

dd = defaultdict(list)
N, K = list(map(int, readline().split()))
for i in range(N):
    t, d = list(map(int, readline().split()))
    heapq.heappush(dd[t], d*-1)

dd = list(dd.values())
dd.sort()

ans = 0
fix = 0
var = []
tmp_max = 0
for i in range(len(dd)):
    fix += heapq.heappop(dd[i]) * -1
    for _ in range(K-(i+1)):
        if len(dd[i]) == 0:
            break
        tmp = heapq.heappop(dd[i]) * -1
        heapq.heappush(var, tmp)
    while len(var) > K-(i+1) and len(var) > 0:
        heapq.heappop(var)
    if len(var) == K-(i+1):
        ans = max(ans , fix+sum(var) + (i+1)**2)


print(ans)

# Optimized solution
# D - Various Sushi
import sys
from collections import defaultdict
import heapq

readline = sys.stdin.readline

dd = defaultdict(list)
N, K = list(map(int, readline().split()))
for i in range(N):
    t, d = list(map(int, readline().split()))
    heapq.heappush(dd[t], d*-1)

dd = list(dd.values())
dd.sort()

ans = 0
fix = 0
var = []
len_var = 0
sum_var = 0
tmp_max = 0

for i in range(min(K, len(dd))):
    fix += heapq.heappop(dd[i]) * -1
    for _ in range(len(dd[i])):
        tmp = heapq.heappop(dd[i]) * -1
        heapq.heappush(var, tmp)
        len_var += 1
        sum_var += tmp
    while len_var > K-(i+1) and len_var > 0:
        del_var = heapq.heappop(var)
        len_var -= 1
        sum_var -= del_var
    if len_var == K-(i+1):
        ans = max(ans , fix+sum_var + (i+1)**2)

print(ans)
# Original solution
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
sushi = [None] * N
for i in range(N):
    t, d = list(map(int, input().split()))
    sushi[i] = (d, t-1)
sushi.sort(reverse=True)

types = set()
cand = []
s = x = 0

for d, t in sushi[:K]:
    if t in types:
        heappush(cand, d)
    else:
        types.add(t)
        x += 1
    s += d

ans = s + x*x
for d, t in sushi[K:]:
    if t in types:
        continue
    if not cand:
        break
    dr = heappop(cand)
    s += d - dr
    types.add(t)
    x += 1
    ans = max(ans, s + x*x)
print(ans)



# Optimized solution
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
sushi = [None] * N
for i in range(N):
    t, d = list(map(int, input().split()))
    sushi[i] = (d, t)
sushi.sort(reverse=True)

types = set()
cand = []
s = x = 0

for d, t in sushi[:K]:
    if t in types:
        cand.append(d)
    else:
        types.add(t)
        x += 1
    s += d
cand.sort(reverse=True)

ans = s + x*x
for d, t in sushi[K:]:
    if t in types:
        continue
    if not cand:
        break
    dr = cand.pop()
    s += d - dr
    types.add(t)
    x += 1
    ans = max(ans, s + x*x)
print(ans)
# Original solution
import sys
input = sys.stdin.readline

N, K = list(map(int,input().split()))
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=lambda x: (x[0],x[1]),reverse=True)

x= []
y= []
y.append(td[0][1])
for i in range(1,N):
    if td[i][0] != td[i-1][0]:
        y.append(td[i][1])
    else:
        x.append(td[i][1])
x.sort(reverse=True)
y.sort(reverse=True)
ans = 0
for i in range(1,min(K,len(y))+1):
    ans = max(ans, sum(y[:i])+sum(x[:max(0,K-i)])+i*i)
print(ans)


# Optimized solution
import sys
input = sys.stdin.readline

N, K = list(map(int,input().split()))
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=lambda x: (x[0],x[1]),reverse=True)

x= []
y= []
y.append(td[0][1])
for i in range(1,N):
    if td[i][0] != td[i-1][0]:
        y.append(td[i][1])
    else:
        x.append(td[i][1])
x.sort(reverse=True)
y.sort(reverse=True)
ans = 0
sum_y = 0
sum_x = []
tmp = 0
sum_x.append(0)
for i in range(len(x)):
    tmp += x[i]
    sum_x.append(tmp)

for i in range(1,min(K,len(y))+1):
    sum_y += y[i-1]
    if len(sum_x) < K-i+1: continue
    ans = max(ans, sum_y + sum_x[K-i] + i*i)
    
print(ans)
# Original solution
from itertools import accumulate
N,K = list(map(int,input().split()))
td = [tuple(map(int,input().split())) for i in range(N)]

td = [(x[0]-1,x[1]) for x in td]
td.sort(key=lambda x:-x[1])

t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
tdK = td[:K]
for i in range(K):
    t[tdK[i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if d_top[td[i][0]] == 0:
        d_top[td[i][0]] = td[i][1]
    else:
        d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])
l = len(t_used)
s = sum(d_top)
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))

if len(d_rest) == 0:
    print((l**2 + s))
else:
    s += d_rest_cum[-1]
    ans = l**2 + s
    for k in range(min(len(d_rest),len(d_candi))):
        ans = max((l+k+1)**2 + s + d_candi_cum[k] - d_rest_cum[k],ans)

    print(ans)

# Optimized solution
N,K = list(map(int,input().split()))
td = [list(map(int,input().split())) for _ in range(N)]
td.sort(key=lambda x:-x[1])
l,r = td[:K],td[K:]
used_l = [0]*N
for i in range(K):
    used_l[l[i][0]-1] += 1

remove = []
for i in range(K-1,-1,-1):
    if used_l[l[i][0]-1] >= 2:
        remove.append(l[i][1])
        used_l[l[i][0]-1] -= 1

used_r = used_l.copy()
add = []
for i in range(N-K):
    if used_r[r[i][0]-1] == 0:
        add.append(r[i][1])
        used_r[r[i][0]-1] += 1

t = sum(used_l)

ans = t**2
for i in range(K):
    ans += l[i][1]

ref = ans
for i in range(min(len(remove),len(add))):
    ref += (t+1)**2-t**2+add[i]-remove[i]
    t += 1
    ans = max(ans,ref)

print(ans)