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

import fractions
from functools import reduce

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

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

ans = 0
if n == 2:
    ans = max(aList)
else:
    for i in range(0,n):
        tmp = aList.pop(0)
        r = gcd_numbers(aList)
        if ans < r:
            ans = r
        aList.append(tmp)

print(ans)

### FIXED CODE ###

import fractions

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

def gcd3(nums):
    ans1 = fractions.gcd(nums[0], nums[1])
    ans2 = fractions.gcd(nums[0], nums[2])
    ans3 = fractions.gcd(nums[1], nums[2])

    if ans1 >= ans2 and ans1 >= ans3:
        return ans1, nums[2]
    if ans2 >= ans1 and ans2 >= ans3:
        return ans2, nums[1]
    if ans3 >= ans1 and ans3 >= ans2:
        return ans3, nums[0]

ans = 0
if n == 2:
    ans = max(aList)
else:
    sList = []
    sList.append(aList.pop(0))
    sList.append(aList.pop(0))
    sList.append(aList.pop(0))
    ans, v = gcd3(sList)

    for i in range(len(aList)):
        tmp = aList.pop(0)
        tmp1 = fractions.gcd(ans, v)
        tmp2 = fractions.gcd(ans, tmp)
        if tmp1 >= tmp2:
            ans = tmp1
            v = tmp
        else:
            ans = tmp2

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

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] < INF:
            continue
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])
        que.append(ny * W + nx)

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

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

s = list(input())
s.reverse()
s.append('0')

dp = [[1000000000] * 2 for _ in range(1000005)]
dp[0][0] = 0
n = len(s)
for i in range(n):
    for j in range(2):
        x = int(s[i])
        x += j
        if x < 10:
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)
        if x > 0:
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))

ans = dp[n][0]
print(ans)

### FIXED CODE ###

s = list(input())
s.reverse()
s.append('0')

dp = [[1000000000] * 2 for _ in range(1000005)]
dp[0][0] = 0
n = len(s)
for i in range(n):
    for j in range(2):
        x = int(s[i])
        x += j
        if x < 10:
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)
        if x > 0:
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))

ans = dp[n][0]
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from itertools import accumulate, product

N = int(input())
A = list(map(int, input().split()))
S = list(accumulate(A))
T = sum(A)
ans = 10**16

for j in range(1, N-1):
    PQ = S[j]
    RS = T - S[j]
    #print("PQ RS", PQ, RS)
    
    i1 = bisect(S, PQ/2) - 1
    i2 = bisect_left(S, PQ/2)
    
    k1 = bisect(S, RS/2 + PQ) - 1
    k2 = bisect_left(S, RS/2 + PQ)
    
    for i, k in product([i1, i2], [k1, k2]):
        #print(i, j, k)
        if i < 0 or i==j or j == k or k == N-1:
            continue
        PQRS = [S[i], S[j] - S[i], S[k] - S[j], T - S[k]]
        #print(PQRS)
        ans = min(ans, abs(max(PQRS) - min(PQRS)))

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from itertools import accumulate, product

N = int(input())
A = list(map(int, input().split()))
S = list(accumulate(A))
T = sum(A)
ans = 10**16

for j in range(1, N-1):
    PQ = S[j]
    RS = T - S[j]
    #print("PQ RS", PQ, RS)
    
    i1 = bisect(S, PQ/2) - 1
    i2 = bisect_left(S, PQ/2)
    
    k1 = bisect(S, RS/2 + PQ) - 1
    k2 = bisect_left(S, RS/2 + PQ)
    
    for i, k in product([i1, i2], [k1, k2]):
        #print(i, j, k)
        if i < 0 or i==j or j == k or k == N-1:
            continue
        PQRS = [S[i], S[j] - S[i], S[k] - S[j], T - S[k]]
        #print(PQRS)
        ans = min(ans, abs(max(PQRS) - min(PQRS)))

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

n, k = map(int,input().split())
a = list(map(int,input().split()))
cnt = [0] * n
ans = 0
for i in a:
    cnt[i-1] += 1

if len(set(a)) <= k:
    print(0)
    exit()
else:
    for i in sorted(cnt):
        if i == 0:
            continue
        else:
            ans += i
            k += 1
            if len(set(a)) <= k:
                print(ans)
                exit()

### FIXED CODE ###

import collections as co

n, k = map(int,input().split())
a = list(map(int,input().split()))
cnt = co.Counter(a)
ans = 0
initial = len(cnt)
if initial <= k:
    print(0)
    exit()
else:
    cnt = sorted(cnt.values())
    for i in range(initial-k):
        ans += cnt[i]
    print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()

C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a in A:
    if C[a] >= 2:
        ans += 1
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)

### FIXED CODE ###

from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

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

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=1024
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
P = list(map(int, input().split()))
Ans = [0]*N
for i in range(N-K+1):
    Ans[i] = sum(P[i:i+K])+K

print(max(Ans)/2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
P = list(map(int, input().split()))
Ans = sum(P[0:K])+K
Ans_max = Ans

for i in range(0,N-K):
    A = P[i]
    B = P[i+K] 
    Ans = Ans+B-A
    if B > A:
        Ans_max = max(Ans_max, Ans)
    
print(Ans_max/2)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())

i,j,k = 0,0,0

ans = 0

while True:
	temp = i * r
	j,k = 0,0
	if(temp > n):
		break
	while True:
		temp = i * r + j * g
		k = 0
		if(temp > n):
			break
		while True:
			temp = i * r + j * g + k * b
			#print(temp)
			if(temp > n): break
			if (temp == n):
				ans += 1
			k += 1
		j+= 1
	i += 1

print(ans)

### FIXED CODE ###

r,g,b,n = map(int,input().split())

i,j,k = 0,0,0

ans = 0



while True:
	temp = i * r
	j,k = 0,0
	if(temp > n):
		break
	while True:
		temp = i * r + j * g
		k = 0
		if(temp > n):
			break
		if((n - temp)%b == 0):
			ans+= 1
		j+= 1
	i += 1

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

l,r=map(int,input().split())
g = list([i%2019 for i in range(l,r+1)])
min=2020
for i in range(len(g)-1):
    for j in range(i+1,len(g)):
        if(min>g[i]*g[j]%2019):
            min=g[i]*g[j]%2019
print(min)

### FIXED CODE ###

l,r=map(int,input().split())
if r - l >= 2019:
    print(0)
    exit()
g = list([i%2019 for i in range(l,r+1)])
m=[]
for i in range(len(g)-1):
    for j in range(i+1,len(g)):
        m.append(g[i]*g[j]%2019)
print(min(m))
### BUGGY CODE ###

n = int(input())

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

sum = a[0]

for i in range(1,len(a)):
    sum = sum * a[i]
    if 0 in a:
        sum = 0
        break
    elif sum > 10**18:
        break
    


if sum > 10**18:
    print(-1)
else:
    print(sum)

### FIXED CODE ###

n = int(input())

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

if 0 in a:
        sum = 0
else:
    for i in range(1,len(a)):
        sum = sum * a[i]
        if sum > 10**18:
            break
        


if sum > 10**18:
    print(-1)
else:
    print(sum)
### BUGGY CODE ###

if __name__ == "__main__":
  n = int(input())
  nums = list(map(int, input().split()))
  result = 1
  for i in nums:
    result *= i
  print(result if result <= 1000000000000000000 else "-1")

### FIXED CODE ###

def main():
  n = int(input())
  nums = list(map(int, input().split()))
  result = 1
  if 0 in nums:
    print(0)
    return
  else:
    for i in nums:
      result *= i
      if result > 1000000000000000000:
        print(-1)
        return
    print(result)
    return


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


import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools
import math
import copy

H, W = map(int, input().split())

A = []
B = []
for _ in range(H):
    a = list(map(int, input().split()))
    A.append(a)

for _ in range(H):
    b = list(map(int, input().split()))
    B.append(b)

C = []
for i in range(H):
    cs = []
    for j in range(W):
        c = abs(A[i][j] - B[i][j])
        cs.append(c)

    C.append(cs)

D = [[[False for _ in range(H*W*80)] for _ in range(W)] for _ in range(H)]

D[0][0][C[0][0]] = True

# print(D[0][0])

for i in range(1, H+W-1):
    #print("i", i)
    for j in range(i+1):
        #print("j", j)
        x = i - j
        y = j
        #print("x", x, "y", y)

        if 0 <= x <= H-1 and 0 <= y <= W - 1:
            if 0 <= x-1 <= H-1:
                for n, bl in enumerate(D[x-1][y]):
                    if not bl:
                        continue
                    # print(n)

                    n2 = n + C[x][y]
                    D[x][y][n2] = True

                    n2 = abs(n - C[x][y])
                    D[x][y][n2] = True

            if 0 <= y-1 <= W-1:
                for n, bl in enumerate(D[x][y-1]):
                    if not bl:
                        continue

                    # print(n)

                    n2 = n + C[x][y]
                    D[x][y][n2] = True

                    n2 = abs(n - C[x][y])
                    D[x][y][n2] = True

            #print("x", x, "y", y, "dxy",  D[x][y])

ans = 0

for i, bl in enumerate(D[H-1][W-1]):
    if bl:
        ans = i
        break


print(ans)


### FIXED CODE ###


import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools
import math
import copy

H, W = map(int, input().split())

A = []
B = []
for _ in range(H):
    a = list(map(int, input().split()))
    A.append(a)

for _ in range(H):
    b = list(map(int, input().split()))
    B.append(b)

C = []
for i in range(H):
    cs = []
    for j in range(W):
        c = abs(A[i][j] - B[i][j])
        cs.append(c)

    C.append(cs)


X = (H+W) * 80
L = X + X + 1

dp = [[0] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
d = C[0][0]
dp[0][0][X+d] = 1
dp[0][0][X-d] = 1

for r in range(H):
    for c in range(W):
        if r == 0 and c == 0:
            continue

        l = np.zeros(L, np.bool)
        d = C[r][c]

        if r != 0:
            l[d:] |= dp[r-1][c][:L-d]
            l[:L-d] |= dp[r-1][c][d:]

        if c != 0:
            l[d:] |= dp[r][c-1][:L-d]
            l[:L-d] |= dp[r][c-1][d:]

        dp[r][c] = l

dp = dp[-1][-1]
d = np.where(dp)[0] - X
ans = np.abs(d).min()
print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())
arr=[]
arr1=[[] for i in range(100001)]
for i in range(p):
    arr.append(list(map(int,input().split())))
    arr1[arr[i][0]].append(arr[i][1])
for i in range(len(arr1)):
    arr1[i].sort()
for i in range(p):
    print("%06d%06d"%(arr[i][0],arr1[arr[i][0]].index(arr[i][1])+1))

### FIXED CODE ###

import bisect
n,p=map(int,input().split())
arr=[]
arr1=[[] for i in range(100001)]
for i in range(p):
    arr.append(list(map(int,input().split())))
    arr1[arr[i][0]].append(arr[i][1])
for i in range(100001):
    if(len(arr1[i])>1):
        arr1[i].sort()
for i in range(p):
    print("%06d%06d"%(arr[i][0],bisect.bisect_right(arr1[arr[i][0]],arr[i][1])))
    #print("%06d%06d"%(arr[i][0],arr1[arr[i][0]].index(arr[i][1])+1))
### BUGGY CODE ###

import sys
import queue

h, w = list(map(int, input().split()))
l = [input() for _ in range(h)]
checked = [[False for _ in range(w)] for __ in range(h)]

q = queue.Queue()
q.put((0, 0, 1))
checked[0][0] = True
while not q.empty():
    x, y, count = q.get()
    #if checked[y][x]:
    #    continue
    checked[y][x] = True
    if x == w-1 and y == h-1:
        ans = 0
        for i in range(h):
            for j in range(w):
                if l[i][j] == ".":
                    ans += 1
        print(ans-count)
        sys.exit(0)
    if x > 0 and l[y][x-1] == "." and not checked[y][x-1]:
        q.put((x-1, y, count+1))
    if y > 0 and l[y-1][x] == "." and not checked[y-1][x]:
        q.put((x, y-1, count+1))
    if x < w-1 and l[y][x+1] == "." and not checked[y][x+1]:
        q.put((x+1, y, count+1))
    if y < h-1 and l[y+1][x] == "." and not checked[y+1][x]:
        q.put((x, y+1, count+1))
print(-1)

### FIXED CODE ###

import sys
import queue

h, w = list(map(int, input().split()))
l = [input() for _ in range(h)]
checked = [[False for _ in range(w)] for __ in range(h)]

q = queue.Queue()
q.put((0, 0, 1))
while not q.empty():
    x, y, count = q.get()
    if checked[y][x]:
        continue
    checked[y][x] = True
    if x == w-1 and y == h-1:
        ans = 0
        for i in range(h):
            for j in range(w):
                if l[i][j] == ".":
                    ans += 1
        print(ans-count)
        sys.exit(0)
    if x > 0 and l[y][x-1] == "." and not checked[y][x-1]:
        q.put((x-1, y, count+1))
    if y > 0 and l[y-1][x] == "." and not checked[y-1][x]:
        q.put((x, y-1, count+1))
    if x < w-1 and l[y][x+1] == "." and not checked[y][x+1]:
        q.put((x+1, y, count+1))
    if y < h-1 and l[y+1][x] == "." and not checked[y+1][x]:
        q.put((x, y+1, count+1))
print(-1)
### BUGGY CODE ###

S = input()
leng = len(S)

count = [0] * 2019
count[0] = 1

for i in range(leng):
    remainder = int(S[i:]) % 2019
    count[remainder] += 1

res = 0
for cnt in count:
    res += cnt * (cnt - 1) // 2
    
print(res)


### FIXED CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

N, M = map(int, input().split())
B = set()
for i in range(M):
  L, R = map(int, input().split())
  A = set(j for j in range(L, R+1))
  if i == 0:
    B = A
  B = A & B
print(len(B))


### FIXED CODE ###

N, M = map(int, input().split())
maxL = 1
minR = N
for i in range(M):
  L, R = map(int, input().split())
  maxL = max(maxL, L)
  minR = min(minR, R)
print(max(minR - maxL +1, 0))
### BUGGY CODE ###

import numpy as np
import math
import collections
import bisect


def divisor(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


N = int(input())

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

A.sort()

ans = 0
ans = N
for i in range(N):
    divs = divisor(A[i])
    divs.sort()
    Set = set(A[:i])
    #print(A[i], "divs", divs)
    if i < N - 1:
        if A[i] == A[i + 1]:
            ans -= 1
            continue

    for d in divs:
        if i != 0:
            if d in Set:
                ans -= 1
                break
print(ans)


### FIXED CODE ###

import numpy as np
import math
import collections
import bisect
from collections import Counter


N = int(input())

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

A.sort()
Set = set()

Amax = A[len(A) - 1]

counter = Counter(A)
ans = 0
for a in A:
    if a in Set:
        continue
    x = a
    while(x <= Amax):
        Set.add(x)
        x += a

    if counter[a] == 1:
        ans += 1

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

def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret


N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)

max_comb = 0
n = 0
r = 0
n = a[0]
for j in range(1, N):
  if max_comb < nCr(a[0],a[j]):
    max_comb = nCr(a[0],a[j])
    r = a[j]
    
ans = str(n) + " " + str(r)
print(ans)
 

### FIXED CODE ###


N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)

tmp = 10 ** 9
ans = 1
for i in range(1,N):
  if abs(a[0]/2 - a[i]) < tmp:
    tmp = abs(a[0]/2 - a[i])
    ans = a[i]

    
s = str(a[0]) + " " + str(ans)
print(s)
### BUGGY CODE ###

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

maximums = []
remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    else:
        maximums.append(d)
    kinds.add(t)
score = sum(maximums) + sum(remains) + len(kinds)**2

for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    remains.pop()
    maximums.append(d)
    test = sum(maximums) + sum(remains) + len(kinds)**2
    score = max(score, test)

print(score)

### FIXED CODE ###

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

score = 0

remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    kinds.add(t)
    score += d
score += len(kinds)**2

test = score
for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    rm = remains.pop()
    test = test + (d - rm) + (len(kinds)*2 - 1)
    score = max(score, test)

print(score)
### BUGGY CODE ###

n = int(input())

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

rg = range(1, n + 1)

for i in rg:
    c = ls.count(i)
    print(c)


### FIXED CODE ###

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

ls2 =[0 for x in range(n)]
#0がn個のリストを用意する

for x in ls:
    ls2[x - 1] += 1

for x in range(n):
    print(ls2[x])