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

# ABC073 D - joisino's travel
import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
inf=float("inf")
mat=[[inf]*N for _ in range(N)]
dist=[inf]*N
visited=[False]*N
for i in range(M):
    a,b,c=map(int,input().split())
    if mat[a-1][b-1]>c:
        mat[a-1][b-1]=mat[b-1][a-1]=c

for i in range(R):
    r[i]-=1

ans=inf
for i in range(N):
    for j in range(N):
        for k in range(N):
            mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j])

for rr in itertools.permutations(r,R):
    t_sum=0
    for j in range(1,R):
        t_sum+=mat[rr[j-1]][rr[j]]
    ans=min(ans,t_sum)
print(ans)

### FIXED CODE ###

# ABC073 D - joisino's travel
import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
inf=float("inf")
mat=[[inf]*N for _ in range(N)]

for i in range(M):
    a,b,c=map(int,input().split())
    if mat[a-1][b-1]>c:
        mat[a-1][b-1]=mat[b-1][a-1]=c

for i in range(R):
    r[i]-=1

ans=inf
for k in range(N):
    for i in range(N):
        for j in range(N):
            mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j])

for rr in itertools.permutations(r,R):
    t_sum=0
    for j in range(1,R):
        t_sum+=mat[rr[j-1]][rr[j]]
    ans=min(ans,t_sum)
print(int(ans))
### BUGGY CODE ###

N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = sorted(_x)
dis = [0 for z in range(N-1)]
z = [0 for z in range(N)]
ans = 1
if N == 1:
    print(abs(x[0]-start))
else:
    for i in range(N-1):
        dis[i] = x[i+1] - x[i]
    for i in range(N):
        z[i] = abs(x[i]-start)
    D = min(dis)
    ans = 1
    for d in range(2,D+1):
        count = 0
        for j in range(N):
            if z[j] % d == 0:
                count += 1
            else:
                break
        if count == N:
            ans = d
    print(ans)


### FIXED CODE ###

import math
N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = [0 for y in range(N)]
for i in range(N):
    x[i] = abs(_x[i] - start)
g = x[0]
for i in range(N):
    g = math.gcd(g,x[i])
print(g)
ans = 1
### BUGGY CODE ###

n,m,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
b = [0]+list(map(int,input().split()))
s = [0]*(n+1)
t = [0]*(m+1)
x = 0
for i in range(n+1):
    s[i] += x + a[i]
    x = s[i]
x = 0
for i in range(m+1):
    t[i] += x + b[i]
    x = t[i]
#print(s,t)
x = 1
while(1):
#for i in range(30):
    f = 0
    #print(x)
    for j in range(x-min(x,m),min(x,n)+1):
        #print(j,x-j)
        if(s[j]+t[x-j] <= k):
            #print(j,x-j)
                f = 1
                break
    if(f == 0):
        break
    x += 1
print(x-1)

### FIXED CODE ###

n,m,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
b = [0]+list(map(int,input().split()))
s = [0]*(n+1)
t = [0]*(m+1)
x = 0
for i in range(n+1):
    s[i] += x + a[i]
    x = s[i]
if(s[-1] <= k):
    p = n
else:
    for i in range(n+1):
        if(s[i] >= k):
            p = i
            break
x = 0
for i in range(m+1):
    t[i] += x + b[i]
    x = t[i]
if(t[-1] <= k):
    p = min(p,m)
else:
    for i in range(m+1):
        if(t[i] >= k):
            p = max(p,i)
            break
#print(s,t)
while(1):
    f = 0
    for j in range(p-min(p,m),min(p,n)+1):
        #print(j,p-j)
        if(s[j]+t[p-j] <= k):
            #print(j,x-j)
                f = 1
                break
    if(f == 0):
        break
    p += 1
print(p-1)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != 1:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS
	W = [1] * N
	Wlist = []
	visit = [0] * N
	visit[0] = 1
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

	# print(Wlist)
	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	# print(ans_up)

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] == 0:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		self.prev = [None] * N; self.prev[s] = -1
		self.order = []
		while self.Q:
			v = self.Q.popleft()
			self.order.append(v)
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.append(i)


#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	Nedge = [0] * N
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		Nedge[a] += 1; Nedge[b] += 1

	W = [1] * N
	#葉の場合の処理
	# for i in range(N):
	# 	if Nedge[i] == 1:
	# 		W[i] = 1

	BF = BFS(G, 0, N)

	for i in range(N - 1, 0, -1):
		v = BF.order[i]
		W[BF.prev[v]] += W[v]

	Wlist = []
	for i in range(N):
		for j in G.graph[i]:
			if j != BF.prev[i]:
				Wlist.append(W[j])
	for i in range(N):
		Wlist.append(N - W[i])

	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

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

import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
for b in B:
    x = (x + b ) % K 
    C.append(x)
    
# print(B,C)

ans=0
for i in range(N):
    for j in range(i,N):
        # print(i,j)
        # print(A[i:j+1],C[i],C[j+1],(C[j+1]-C[i]) % K)
        if (C[j+1]-C[i]) % K == j-i+1:
            ans = ans + 1 
print(ans)

exit(0)

### FIXED CODE ###

import math
import sys
import bisect
import array

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
i = 0 
for b in B:
    x = (x + b ) % K 
    C.append((x-i-1) % K) 
    i += 1 
    
# print(B,C)

E={}


ans=0
for i in range(N+1):
    if C[i] in E:
        ans += E[C[i]]
        E[C[i]] = E[C[i]] + 1
    else:
        E[C[i]] = 1
    if i >= K-1:
        E[C[i-K+1]] = E[C[i-K+1]] - 1
        if E[C[i-K+1]] == 0:
             E.pop(C[i-K+1])

print(ans)
exit(0)
### BUGGY CODE ###

#!/usr/bin/python3

class UnionFindTree:
    def __init__(self, x):
        self.parent = self
        self.id = x

    def find(self):
        if self.id == self.parent.id:
            return self
        else:
            return self.parent.find()


# main
n, q = map(int, input().split())
nodes = [UnionFindTree(i) for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split())
    x_root = nodes[x].find()
    y_root = nodes[y].find()
    if com == 0:
        # union
        y_root.parent = x_root
    else:
        # same
        same = 1 if x_root.id == y_root.id else 0
        print(same)
            

### FIXED CODE ###

#!/usr/bin/python3

class UnionFindTree:
    def __init__(self, x):
        self.parent = self
        self.id = x
        self.rank = 0

    def find(self):
        if self.id == self.parent.id:
            return self
        else:
            return self.parent.find()


# main
n, q = map(int, input().split())
nodes = [UnionFindTree(i) for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split())
    x_root = nodes[x].find()
    y_root = nodes[y].find()
    if com == 0:
        # union
        if x_root.rank > y_root.rank:
            y_root.parent = x_root
        elif y_root.rank > x_root.rank:
            x_root.parent = y_root
        elif x_root.id != y_root.id:
            y_root.parent = x_root
            x_root.rank += 1
    else:
        # same
        same = 1 if x_root.id == y_root.id else 0
        print(same)
### BUGGY CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod if i > 1])))


### FIXED CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    T = [int(S[i:]) % 2019 if i < len(S) else 0 for i in range(len(S) + 1)]
    M = [0 for _ in range(2019)]
    # M = [T.count(i) for i in range(2019)]
    for t in T:
        M[t] += 1
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    T = [0 for _ in range(len(S) + 1)]
    for i in range(len(S) - 1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * pow(10, len(S) - 1 - i, 2019)) % 2019
    # T = [int(S[i:]) % 2019 if i < len(S) else 0 for i in range(len(S) + 1)]
    M = [0 for _ in range(2019)]
    # M = [T.count(i) for i in range(2019)]
    for t in T:
        M[t] += 1
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

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

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,x=map(int,input().split())
    X=[int(_) for _ in input().split()]
    X.append(x)
    X.sort()
    XX=[0]*n
    for i in range(n):
        XX[i]=X[i+1]-X[i]
    ans=min(XX)
    while True:
        flag=True
        for xx in XX:
            if xx%ans!=0:
                flag=False
        if flag==False:
            ans-=1
        else:
            break
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
import fractions
def input(): return sys.stdin.readline().rstrip()
import math

def main():
    n,x=map(int,input().split())
    X=[int(_) for _ in input().split()]
    X.append(x)
    X.sort()
    ans=X[1]-X[0]
    for i in range(1,n):
        ans=fractions.gcd(ans,X[i+1]-X[i])
    print(ans)

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

n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        xys[i].append((x-1, y))

def digitsum(x):
    ret = 0
    while x>0:
        ret += x & 1
        x <<= 1
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)



### FIXED CODE ###

n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        xys[i].append((x-1, y))

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)
### BUGGY CODE ###

K = int(input())
N = 0

for i in range(K):
    N += 7*(10**i)
    if N % K == 0:
        print(i+1)
        exit()

print(-1)

### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
aaa = list(map(int, input().split()))
ans = 0
MOD = 1_000_000_007
for i in range(N-1):
    for j in range(i + 1, N):
        ans += aaa[i] ^ aaa[j]
        ans %= MOD
print(ans)


### FIXED CODE ###

N = int(input())
aaa = list(map(int, input().split()))
bbb = [format(a, '061b') for a in aaa]

zero = [0] * 61
one = [0] * 61
for i in range(61):
    s = ''.join(list(b[-(i+1)] for b in bbb))
    zero[i] = s.count('0')
    one[i] = s.count('1')
ans = 0
MOD = 1_000_000_007
for i, o, l in zip(range(61), zero, one):
    ans += 2**i * o * l
    ans %= MOD
print(ans)
### BUGGY CODE ###

import math


n = int(input())
a = list(map(int, input().split()))
cnt = {}
for v in a:
    if v not in cnt:
        cnt[v] = 0
    cnt[v] += 1
ans = {}
for key1 in cnt.keys():
    s = 0
    for key2, value in cnt.items():
        if key1 == key2:
            value -= 1
        if value <= 1:
            continue
        s += math.factorial(value)//(2*math.factorial(value-2))
    ans[key1] = s
for v in a:
    print(ans[v])

### FIXED CODE ###

import math
import collections


def nc2(n):
    if n <= 1:
        return 0
    return math.factorial(n)//(2*math.factorial(n-2))


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

cnt = collections.Counter(a)
each_ans = {}
for key, value in cnt.items():
    t = nc2(value)
    each_ans[key] = (t, t-value+1)
all_sum = sum(value[0] for _, value in each_ans.items())
ans = {}
for key in cnt.keys():
    ans[key] = all_sum - each_ans[key][0] + each_ans[key][1]
for i in a:
    print(ans[i])
### BUGGY CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[0]*N,[1]*N,[0]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
            if ta>mod:
                ta %= mod
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
            if tc > mod:
                tc %= mod
        Ans += ta*tc
        if Ans > mod:
            Ans %= mod

print(Ans)

### FIXED CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

n, m = map(int, input().split())
cards = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

c = []
for i in bc:
    for j in range(i[0]):
        c.append(i[1])
        
c.sort(reverse = True)

for i in c:
    if min(cards) < i:
        cards[cards.index(min(cards))] = i
    else:
        break
    
print(sum(cards))

### FIXED CODE ###

n, m = map(int, input().split())
cards = [[1, int(i)] for i in input().split()]
bc = [list(map(int, input().split())) for _ in range(m)]
cards += bc
cards.sort(key = lambda x: x[1], reverse = True)

l = []
flag = 0
for i in cards:
    for j in range(i[0]):
        l.append(i[1])
        if len(l) == n:
            flag = 1
            break
    if flag:
        break

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

import sys
input = sys.stdin.readline

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*(N-1)**2

for i in range((N-1)**2):
    if E[i]==[] and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        if H[fr]>N*N:
            print(-1)
            sys.exit()
        Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

EDGEIN=[0]*(N*N)

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])
        EDGEIN[A[i][j]]+=1

from collections import deque
Q=deque()

for i in range((N-1)**2):
    if EDGEIN[i]==0 and len(E[i])>0:
        Q.append(i)

TOP=[]
while Q:
    x=Q.pop()
    TOP.append(x)
    for to in E[x]:
        EDGEIN[to]-=1
        if EDGEIN[to]==0:
            Q.append(to)


H=[1]*(N**2)
for x in TOP[::-1]:

    for fr in EREV[x]:
            
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1

if min(EDGEIN)<0 or max(EDGEIN)>0:
    print(-1)
else:
    print(max(H))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
for i in range(k):
  if i == n:
    break
  h.remove(max(h))
print(sum(h))

### FIXED CODE ###

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())))
for i in range(k):
  if i == n:
    break
  h.pop(-1)
print(sum(h))
### BUGGY CODE ###

n=int(input())
i=0
j=n//2
print(i)
a=input()
print(j)
b=input()
if j%2and a!=b or not j%2and a==b:
    i,j=j,n
while 1:
    if j-i<2:
        print(j)
        exit()
    k=i+(j-i)//2
    print(k)
    c=input()
    if(k-i)%2and a==c:
        j=k
    else:
        i=k

### FIXED CODE ###

n=int(input())
i=0
j=n-1
print(i)
a=input()
print(j)
b=input()
while 1:
    if j-i<2:
        print(i)
        _=input()
        print(j)
        if input()!='Vacant':
            print('助けてくれ～～～')
    k=(j-i)//2+i
    print(k)
    c=input()
    if(k-i)%2and a==c or not(k-i)%2and a!=c:
        j=k
    else:
        a=c
        i=k
### BUGGY CODE ###

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

def search(x):
    for i in range(n-x):
        
        if s[i:i+x] in s[i+x:]:


            return True

    return False

l = -1
r = n+1
while r > l+1:
    mid = (r+l)//2
    if search(mid):
        l = mid
    else:
        r = mid
print(l)

### FIXED CODE ###

n = int(input())
s = list(input())

def z_algo(s):
    l = len(s)
    count = [0]*l
    i = 1
    j = 0
    count[0] = l
    while i < l:
        while i+j < l and s[i+j] == s[j]:
            j += 1
        count[i] = j
        if j == 0:
            i += 1
            continue
        
        k = 1
        while l - i > k and k < j-count[k]:
            count[i+k] = count[k]
            k += 1
        i += k
        j -= k
    return count
count = 0
for i in range(n):
    ans = z_algo(s[i:])
    for j in range(n-i):
        count = max(count,min(ans[j],j))

print(count)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path
n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]
for i in range(n-1):
    GRAPH[i][i+1] = GRAPH[i+1][i] = 1
GRAPH[x][y] = GRAPH[y][x] = 1
G = np.array(GRAPH)
sp = shortest_path(G)

ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = int(sp[i][j])-1
        ans[path] += 1
print(*ans, sep="\n")


### FIXED CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]

def shortest_path(i, j):
    if i <= x <= y <= j:
        return min(j-i, x-i+j-y+1)
    elif x <= i <= y <= j:
        return min(j-i, i-x+j-y+1)
    elif x <= i <= j <= y:
        return min(j-i, i-x+y-j+1)
    elif i <= x <= j <= y:
        return min(j-i, x-i+y-j+1)
    else:
        return j-i


ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = shortest_path(i, j)-1
        ans[path] += 1
print(*ans, sep="\n")
### BUGGY CODE ###

import itertools
N, K = [int(x) for x in input().split()]
orig_td = [tuple([int(x) for x in input().split()]) for _ in range(N)]
td = orig_td.copy()
INF = 10**9
# print(td)


def score(a):
    kiso = sum([x[1] for x in a])
    # print(a)
    bonus = len(set([x[0] for x in a]))**2
    return kiso + bonus


total = score(td)
for i in range(N, K, -1):
    # print("i", i)
    max_score = -INF
    useless_neta = 0
    for neta in td:
        te = td.copy()
        te.remove(neta)
        kari = score(te)
        if kari > max_score:
            max_score = kari
            useless_neta = neta
    td.remove(useless_neta)
    # print(td)
print(score(td))

# print("全列挙", max([score(x) for x in itertools.permutations(orig_td, K)]))


### FIXED CODE ###

N, K = [int(x) for x in input().split()]
td = sorted([[int(x) for x in input().split()] for _ in range(N)],
            key=lambda x: x[1], reverse=True)
INF = 10**9
# print(td)

first = []
second = []
kind = set()
for i in range(K):
    if td[i][0] not in kind:
        first.append(td[i])
        kind.add(td[i][0])
    else:
        second.append(td[i])

yummy = sum([x[1] for x in first + second])
best_ans = yummy + len(kind)**2

for k in range(K, N):
    if len(second) == 0:
        break
    if td[k][0] in kind:
        continue

    a = second.pop(-1)
    yummy -= a[1]
    kind.add(td[k][0])
    first.append(td[k])
    yummy += td[k][1]
    ans = yummy + len(kind)**2
    # print(first, second, ans)
    if best_ans < ans:
        best_ans = ans
print(best_ans)