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

N = int(input())
def f(a, b, c):
    return a**2 + b**2 + c**2 + a*b + b*c + c*a

for i in range(1, N+1):
    if i < 6:
        print(0)
    else:
        x, y, z = 0, 0, 0
        ans = 0
        while True:
            x += 1
            y = 0
            z = 0
            if f(x,y,z) > i:
                break
            while True:
                y += 1
                z = 1
                s = f(x,y,z)
                if s > i:
                    break
                while s <= i:
                    if s == i:
                        ans += 1
                        break
                    z += 1
        print(ans)

### FIXED CODE ###

N = int(input())
def f(a, b, c):
    return a**2 + b**2 + c**2 + a*b + b*c + c*a
ans = [0] * N

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = f(x,y,z)
            if n <= N:
                ans[n-1] += 1
for a in ans:
    print(a)
### BUGGY CODE ###

S = list(map(int, input()))
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x += s*(10**i)
    d[x%2019] += 1
  ans = 0
  for m in d:
    ans += m*(m-1)//2
  print(ans)



### FIXED CODE ###

S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x = (x+int(s)*pow(10,i,2019))%2019
    d[x] += 1
  print(sum([m*(m-1)//2 for m in d]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import random

D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]

sumC = sum(C)
def score(strategy):
    sat = 0
    last = [0]*26
    for i,ind in enumerate(strategy):
        last = [l+1 for l in last]
        last[ind] = 0
        sat -= sum((c*l for c,l in zip(C,last)))
        sat += S[i][ind]
    return sat

#first = [np.argmax(ds) for ds in S]
first = [i % 26 for i in range(D)]

ans = first
now_score = score(ans)

for i in range(5):
    for d in range(D):
        temp = ans[:]
        temp[d] = S[d].index(max(S[d]))
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for i in range(10):
    samples = [random.randint(0,25) for j in range(D)]
    for d in range(D):
        temp = ans[:]
        temp[d] = samples[d]
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for i in range(5):
    for d in range(D):
        temp = ans[:]
        temp[d] = S[d].index(max(S[d]))
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for a in ans:
    print(a+1)



### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

D = int(input())
C = np.array(list(map(int,input().split())),dtype=np.int)
S = np.array([list(map(int,input().split())) for i in range(D)],dtype=np.int)

sumC = sum(C)
def score(strategy):
    sat = 0
    last = np.zeros(26).astype(np.int)
    for i,ind in enumerate(strategy):
        last += 1
        last[ind] = 0
        sat -= np.sum(C * last)
        sat += S[i][ind]
    return sat

#first = [np.argmax(ds) for ds in S]
first = [i % 26 for i in range(D)]

ans = first
now_score = score(ans)

for i in range(1):
    samples = np.random.randint(0,26,size=D).tolist()
    for d in range(D):
        temp = ans[:]
        temp[d] = samples[d]
        if score(temp) > now_score:
            ans = temp

for a in ans:
    print(a+1)
### BUGGY CODE ###

#C
n = int(input())
h = list(map(int,input().split()))
tmp = 0
prev = True
result = [0 for _ in range(n)]

for i in range(n-1):
    if prev:
        for j in range(i,n-1):
            if h[j] >= h[j+1]:
                tmp += 1
            else:
                break
    if tmp > 0:
        prev = False
    else:
        prev = True
        
    result[i] = tmp
    tmp = 0
    
print(max(result))
            

### FIXED CODE ###

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

a,b = 0,0

for i in range(n-1):
    if h[i] >= h[i+1]:
        a += 1
        b = max(b,a)
    else:
        a = 0
        
print(b)
### BUGGY CODE ###

from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
b = [0]*(n-len(b))+b
c = list(accumulate([0]+b))

for k in range(1,n+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    print(l)




### FIXED CODE ###

from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

print(n)
for k in range(2,n//2+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    print(l)

for k in range(max(n//2+1,2),n+1):
    if exist>=k:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

#ABC120C-Unification.py

from sys import stdin

input = stdin.readline

S = input().rstrip()

Nblock = 0

while '0' in S and '1' in S:
    s = S.split('01')
    Nblock += (len(s)-1)*2
    S = ''.join(s)
    t = S.split('10')
    Nblock += (len(t)-1)*2
    S = ''.join(t)


print(Nblock)


### FIXED CODE ###

#ABC120C-Unification.py

from sys import stdin

input = stdin.readline

S = input().rstrip()

Nblock = min(S.count('1'), S.count('0'))

print(Nblock*2)
### BUGGY CODE ###

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = 0
for i in range(2**N):
    X=0
    Y=0
    for j in range(N):
        if((i>>j)&1):
            X+=V[j]
            Y+=C[j]
        if X-Y>ans:
            ans = X-Y
print(ans)

### FIXED CODE ###

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))
V_C = [V[i]-C[i] for i in range(N)]
ans = 0
for i in range(N):
    if V_C[i]>0:
        ans += V_C[i]
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

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

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

for i in range(n-1):
    a, b = map(int, input().split())
    adjs[a].append(b)
    adjs[b].append(a)

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

visited = set()
queue = deque()
queue.append(1)

while len(queue) > 0:
    a = queue.popleft()
    visited.add(a)
    for b in adjs[a]:
        if b in visited:
            continue
        counts[b] += counts[a]
        queue.append(b)

print(' '.join(list(map(lambda x: str(x), counts[1:]))))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

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

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

for i in range(n-1):
    a, b = map(int, input().split())
    adjs[a].append(b)
    adjs[b].append(a)

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

visited = set()
queue = deque()
queue.append(1)

while len(queue) > 0:
    a = queue.popleft()
    visited.add(a)
    for b in adjs[a]:
        if b in visited:
            continue
        counts[b] += counts[a]
        queue.append(b)

for c in counts[1:]:
    print(c, end=" ")
print()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort()
s=set()
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            s.add(x)
            B.append(x)
        else:
            s.add(x)
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
    else:
        s.add(x)
        B.append(x)
        
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans=0
for x in B:
    div=make_divisors(x)
    for j in div:
        if j==1:
            if x==1:
                continue
            else:
                if j in s:
                    break
        elif j==x:
            continue
        elif x%j==0:
            if x//j in s or j in s:
                break
    else:
        ans+=1
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
bl=[0]*(10**6+1)
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            B.append(x)
        else:
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
            xx=x
            while x<=10**6:
                bl[x]=1
                x+=xx
    else:
        B.append(x)


ans=0
for x in B:
    ans+=not bl[x]
    xx=x
    while x<=10**6:
        bl[x]=1
        x+=xx
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
import numpy as np

def ln():
    return map(int, input().split())

N,M = ln()
A = list(ln())

SUM = np.zeros(N+1,dtype = int)

for i in range(N):
    SUM[i+1] = SUM[i] + A[i]
    SUM[i+1] %= M
ans = 0

for i in range(N):
    ans += np.sum(SUM[i+1:] == SUM[i])

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
import numpy as np

def ln():
    return map(int, input().split())

N,M = ln()

AA = list(ln())
A = np.array(AA)

SUM = np.zeros(N+1,dtype = int)
for i in range(N):
    SUM[i+1] = (SUM[i] + A[i]) % M

ans = 0
dic = dict()
# for i in range(N):
#     dic[SUM[i]] = 1
for i in range(N+1):
    if SUM[i] in dic:
        dic[SUM[i]] += 1
    else:
        dic[SUM[i]] = 1
    ans += dic[SUM[i]] -1


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

s = input()
a = list(map(int,input().split()))
mod = 1000000007
ans = 0
while True:
    l_f = a[0]
    del a[0]
    if len(a) < 1: break
    for i in a:
        ans += l_f * i
print(ans%mod)

### FIXED CODE ###

s = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
ans = 0
sum_a = sum(a)
for i in range(s):
    sum_a -= a[i]
    ans += sum_a * a[i] % mod
print(ans%mod)
### BUGGY CODE ###

# -*- using:utf-8 -*-
from itertools import combinations

if __name__ == "__main__":
  n = int(input())
  li = list(map(int, input().split()))
  array = list(combinations(li, 2))
  sum = 0
  mod = 1000000007
  for i in range(len(array)):
    sum += array[i][0] * array[i][1]
  ans = sum % mod
  print(ans)

### FIXED CODE ###

# -*- using:utf-8 -*-

class main:
  def function(n, a):
    mod = 10 **9 +7
    S = [0] * (n + 1)
    for i in range(n):
      S[i + 1] = S[i] + a[i]
    SN = S[-1]
    ans = 0
    for i in range(n - 1):
      cnt = a[i] * (SN - S[i + 1])
      ans += cnt
    print(ans % mod)



if __name__ == "__main__":
  n = int(input())
  a = list(map(int, input().split()))
  main.function(n,a)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 **9 + 7

ni = [0 for _ in range(60)]
for i in range(N):
    tmp = A[i]
    count = 0
    while(True):
        if tmp % 2 == 1:
            ni[count] += 1
        count += 1
        tmp = tmp // 2
        if tmp == 0:
            break
ans = 0
for j in range(60):
    ans += (ni[j] * (N-ni[j])) * 2 ** j 

print(ans%MOD)


    


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 **9 + 7
 
ni = [0 for _ in range(60)]
for i in range(N):
    tmp = A[i]
    count = 0
    while(True):
        if tmp % 2 == 1:
            ni[count] += 1
        count += 1
        tmp = tmp // 2
        if tmp == 0:
            break
ans = 0
for j in range(60):
    ans += (ni[j] * (N-ni[j])) * 2 ** j 
 
print(ans%MOD)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors



n=int(input())
count=0
for c in range(1,n+1):
	ab=n-c
	tmp=len(make_divisors(ab))
	count+=tmp

print(count)

### FIXED CODE ###

n=int(input())
count=0
for a in range(1,n+1):
	count+=(n-1)//a

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

# your code goes here
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]

ans = 1145141919810
for i in range(C):
	for j in range(C):
		if j == i:
			continue
		for k in range(C):
			if k == i or k == j:
				continue
			tmp = 0
			for x in range(N):
				for y in range(N):
					if (x+y+2)%3==2:
						tmp+= D[c[x][y]-1][i]
					elif (x+y+2)%3==0:
						tmp+= D[c[x][y]-1][j]
					else:
						tmp+= D[c[x][y]-1][k]
			ans = min(ans,tmp)
print(ans)


### FIXED CODE ###

# your code goes here
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]

Color = [[0 for i in range(C)] for j in range(3)]

for x in range(N):
	for y in range(N):
		Color[(x+y+2)%3][c[x][y]-1] += 1

ans = 1145141919810
for i in range(C):
	for j in range(C):
		if j == i:
			continue
		for k in range(C):
			if k == i or k == j:
				continue
			tmp = 0
			for x in range(3):
				for y in range(C):
					if x == 0:
						tmp += Color[x][y]*D[y][i]
					elif x == 1:
						tmp += Color[x][y]*D[y][j]
					else:
						tmp += Color[x][y]*D[y][k]
			ans = min(ans,tmp)
print(ans)
### BUGGY CODE ###

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

INF = 10 ** 9
dist1 = [[INF] * N for _ in range(N)]
for i in range(N):
    dist1[i][i] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    dist1[A][B] = C
    dist1[B][A] = C

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

dist2 = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dist1[i][j] <= L:
            dist2[i][j] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if dist2[s][t] >= INF:
        print (-1)
    else:
        print (dist2[s][t] - 1)

### FIXED CODE ###

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

INF = 10 ** 18
dist1 = [[INF] * N for _ in range(N)]
for i in range(N):
    dist1[i][i] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    dist1[A][B] = C
    dist1[B][A] = C

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

dist2 = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dist1[i][j] <= L:
            dist2[i][j] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if dist2[s][t] >= INF:
        print (-1)
    else:
        print (dist2[s][t] - 1)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
from bisect import bisect_left
ans = 0
for i1 in range(N-2):
  for i2 in range(i1+1,N-1):
    l1,l2 = L[i1],L[i2]
    th = bisect_left(L[i2+1:],l1+l2)
    #print(l1,l2,L[i2+1:],(l2-l1+1)*(-1),th)
    ans += th
print(ans)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
from bisect import bisect_left
ans = 0
for i1 in range(N-2):
  for i2 in range(i1+1,N-1):
    l1,l2 = L[i1],L[i2]
    #th = bisect_left(L[i2+1:],l1+l2)
    #print(l1,l2,L[i2+1:],(l2-l1+1)*(-1),th)
    th = bisect_left(L,l1+l2)
    ans += max(th-i2-1,0)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N,Q = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]
counter = []
ab.append([0,1])
ab.sort()
px.sort()
px_shin =[0 for i in range(N)]
temp=0
def dfs(p,x):
    for i in range(N):
        if ab[i][0] == p:
            for j in range(Q):##
                if px[j][0] == ab[i][1]:
                    px_shin[ab[i][1]-1] += px[j][1]
            px_shin[ab[i][1]-1]+=x
            dfs(ab[i][1], px_shin[ab[i][1]-1])
        
dfs(0,0)
print(' '.join(map(str, px_shin)))



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N,Q = map(int,input().split())
to = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

for _ in range(N-1):
    a,b=map(int,input().split())
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

def dfs(v, p):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
dfs(1, -1)
print(*ans[1:])
### BUGGY CODE ###

import fractions
from functools import reduce

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

k = int(input())

# # nは組み合わせの数
# n = k**3

L = []
for i in range(1, k+1):
    for j in range(1, k+1):
        for p in range(1, k+1):
            L.append(gcd(i, j, p))

print(sum(L))

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

L = []
for i in range(1, k+1):
    for j in range(1, k+1):
        for p in range(1, k+1):
            L.append(gcd(i, j, p))

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

import numpy as np

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j < a[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-a[i]] + b[i])
    return min(dp[N][H:Hmax+1])


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [[INF for _ in range(Hmax+1)] for _ in range(N+1)] 
dp[0][0] = 0
print(rec_z())

### FIXED CODE ###

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
from collections import deque
if A+B-1>N or N>A*B:
    print(-1)
else:
    blocks = [deque() for _ in range(A)]
    cnt = N
    blocks[0] = list(range(B, 0, -1))
    flg = True
    while flg:
        flg = False
        for i in range(A-1, 0, -1):
            blocks[i].append(cnt)
            cnt -= 1
            if cnt==B:
                break
        else:
            flg = True
    ans = [0]*N
    cnt = 0
    for b in blocks:
        for a in b:
            ans[cnt] = str(a)
            cnt += 1
    print(' '.join(ans))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
from collections import deque
if A+B-1>N or N>A*B:
    print(-1)
else:
    blocks = []
    blocks.append(' '.join(map(str, range(B, 0, -1))))
    now = B+1
    rest = N-A+2

    while now:
        if now>=rest:
            break
        if now+B>rest:
            blocks.append(' '.join(map(str, range(rest, now-1, -1))))
            rest += 1
            break
        blocks.append(' '.join(map(str, range(now+B-1, now-1, -1))))
        now = now+B
        rest += 1
    blocks.append(' '.join(map(str, range(rest, N+1))))
    print(' '.join(blocks))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    K,S = map(int, input().split())
    n = 0
    for i in range(K+1):
        x = min(K+1, S-i+1)
        for j in range(x):
            y = min(K+1, S-i-j+1)
            for k in range(y):
                if i+j+k == S:
                    n += 1
    print(n)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    K,S = map(int, input().split())
    n = 0
    for i in range(K+1):
        for j in range(K+1):
            if S-i-j >= 0 and S-i-j <= K:
                n += 1
    print(n)

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

import sys
import heapq as h

input=sys.stdin.readline

N,K=map(int,input().split())
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=map(int,input().split())
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
h.heapify(extra)
need=[]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if sushi[i] in need:
            h.heappush(extra,sushi[i][0])
        else:
            need.append(sushi[i])
    else:
        h.heappush(extra,sushi[i][0])


appendix=[-kindmax[i] for i in range(0,N) if kindmax[i]!=0 and (not i in kind)]
h.heapify(appendix)

k=len(kind)
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum-=h.heappop(appendix)+h.heappop(extra)
    test=k**2+sum
    if test>ans:
        ans=test

print(ans)

### FIXED CODE ###

import sys
import heapq as h

input=sys.stdin.readline

N,K=map(int,input().split())
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=map(int,input().split())
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
flag=[0 for i in range(0,N+1)]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if flag[sushi[i][1]]==1:
            extra.append(sushi[i][0])
        else:
            flag[sushi[i][1]]=1
    else:
        extra.append(sushi[i][0])


set={i for i in range(1,N+1)}
set-=kind
appendix=[kindmax[i] for i in set if kindmax[i]!=0 ]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

print(ans)